<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.4.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">
  <meta name="google-site-verification" content="_hgg1Y3vl6FDA0y9ycG3MRMdmBljtivpN0MGPBl9Vks">
  <meta name="baidu-site-verification" content="code-BjkBUVTz39">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="//fonts.googleapis.com/css?family=Noto Serif SC:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"wangduwei.top","root":"/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":true,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":"gitalk | valine","storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

<script data-ad-client="ca-pub-8087648226243491" async src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>

  <meta property="og:type" content="website">
<meta property="og:title" content="嗅不到北的狗子">
<meta property="og:url" content="https://wangduwei.top/archives/index.html">
<meta property="og:site_name" content="嗅不到北的狗子">
<meta property="og:locale" content="zh_CN">
<meta property="article:author" content="wangduwei">
<meta name="twitter:card" content="summary">

<link rel="canonical" href="https://wangduwei.top/archives/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : true,
    isPost : false,
    lang   : 'zh-CN'
  };
</script>

  <title>嗅不到北的狗子</title>
  
    <script async src="https://www.googletagmanager.com/gtag/js?id=G-69Z1P1CBTV"></script>
    <script>
      if (CONFIG.hostname === location.hostname) {
        window.dataLayer = window.dataLayer || [];
        function gtag(){dataLayer.push(arguments);}
        gtag('js', new Date());
        gtag('config', 'G-69Z1P1CBTV');
      }
    </script>


  <script>
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?9f3c7bb2232e1e3fda4c019e4a4406c0";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

<link rel="alternate" href="/atom.xml" title="嗅不到北的狗子" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">嗅不到北的狗子</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a>

  </li>
        <li class="menu-item menu-item-sitemap">

    <a href="/sitemap.xml" rel="section"><i class="fa fa-sitemap fa-fw"></i>站点地图</a>

  </li>
  </ul>
</nav>




</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content index posts-expand">
            
      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://wangduwei.top/kotlin-lang-sequence.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpeg">
      <meta itemprop="name" content="wangduwei">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="嗅不到北的狗子">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/kotlin-lang-sequence.html" class="post-title-link" itemprop="url">高效Kotlin-51：使用Sequence优化集合操作</a>
        </h2>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>
              

              <time title="创建时间：2021-11-06 21:37:43 / 修改时间：22:47:39" itemprop="dateCreated datePublished" datetime="2021-11-06T21:37:43+08:00">2021-11-06</time>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/kotlin-lang-sequence.html#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/kotlin-lang-sequence.html" itemprop="commentCount"></span>
    </a>
  </span>
  
  <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="far fa-file-word"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>7.9k</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="far fa-clock"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>7 分钟</span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h4 id="一、概述"><a href="#一、概述" class="headerlink" title="一、概述"></a>一、概述</h4><p>你可能对 <code>Iterable</code> 和 <code>Sequence</code> 傻傻分不清。看一下他们的代码：</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">interface</span> <span class="title">Iterable</span>&lt;<span class="type">out T</span>&gt; </span>&#123;</span><br><span class="line">    <span class="keyword">operator</span> <span class="function"><span class="keyword">fun</span> <span class="title">iterator</span><span class="params">()</span></span>: Iterator&lt;T&gt;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">interface</span> <span class="title">Sequence</span>&lt;<span class="type">out T</span>&gt; </span>&#123;</span><br><span class="line">    <span class="keyword">operator</span> <span class="function"><span class="keyword">fun</span> <span class="title">iterator</span><span class="params">()</span></span>: Iterator&lt;T&gt;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>好像只有名字不一样-_-||，但他们却有着本质的区别。<code>Sequence</code>属于懒加载，中间操作符不会触发计算，仅仅是对前一个Sequence的装饰，只有在遇到toList()或count()这些终止操作符时才会执行真正的计算工作。而Iterable每一步都返回一个新的集合。</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">inline</span> <span class="function"><span class="keyword">fun</span> <span class="type">&lt;T&gt;</span> Iterable<span class="type">&lt;T&gt;</span>.<span class="title">filter</span><span class="params">(</span></span></span><br><span class="line"><span class="params"><span class="function">    predicate: (<span class="type">T</span>) -&gt; <span class="type">Boolean</span></span></span></span><br><span class="line"><span class="params"><span class="function">)</span></span>: List&lt;T&gt; &#123;</span><br><span class="line">    <span class="keyword">return</span> filterTo(ArrayList&lt;T&gt;(), predicate)</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="function"><span class="keyword">fun</span> <span class="type">&lt;T&gt;</span> Sequence<span class="type">&lt;T&gt;</span>.<span class="title">filter</span><span class="params">(</span></span></span><br><span class="line"><span class="params"><span class="function">    predicate: (<span class="type">T</span>) -&gt; <span class="type">Boolean</span></span></span></span><br><span class="line"><span class="params"><span class="function">)</span></span>: Sequence&lt;T&gt; &#123;</span><br><span class="line">    <span class="keyword">return</span> FilteringSequence(<span class="keyword">this</span>, <span class="literal">true</span>, predicate)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>下图中filter操作符不做任何计算操作，只是返回一个装饰器对象，在遇到toList()操作符才执行计算。</p>
<center>
    <img src="../images/kotlin_sequence_operation.jpeg" width="500"/>
</center>

<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">val</span> seq = sequenceOf(<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>)</span><br><span class="line"><span class="keyword">val</span> filtered = seq.filter &#123; print(<span class="string">&quot;f<span class="variable">$it</span> &quot;</span>); it % <span class="number">2</span> == <span class="number">1</span> &#125;</span><br><span class="line">println(filtered)  <span class="comment">// FilteringSequence@...</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">val</span> asList = filtered.toList()</span><br><span class="line"><span class="comment">// f1 f2 f3</span></span><br><span class="line">println(asList) <span class="comment">// [1, 3]</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">val</span> list = listOf(<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>)</span><br><span class="line"><span class="keyword">val</span> listFiltered = list</span><br><span class="line">    .filter &#123; print(<span class="string">&quot;f<span class="variable">$it</span> &quot;</span>); it % <span class="number">2</span> == <span class="number">1</span> &#125;</span><br><span class="line"><span class="comment">// f1 f2 f3</span></span><br><span class="line">println(listFiltered) <span class="comment">// [1, 3]</span></span><br></pre></td></tr></table></figure>

<h4 id="二、优势"><a href="#二、优势" class="headerlink" title="二、优势"></a>二、优势</h4><p>Sequence的惰性执行有以下几个优点：</p>
<ul>
<li>保证操作的顺序性</li>
<li>保证操作执行次数最少化</li>
<li>他们可以是无限的</li>
<li>无需每一步创建新的集合</li>
</ul>
<p>下面依次讨论一下这些优点</p>
<h5 id="一、顺序性很重要"><a href="#一、顺序性很重要" class="headerlink" title="一、顺序性很重要"></a>一、顺序性很重要</h5><table>
    <tr>
        <td>使用Sequence处理数据时，每个元素依次执行所有操作符。这是一种元素接元素的处理方式。</td>
        <td>使用Iterable处理数据时，每个操作符依次执行所有数据。这是一种步骤接步骤的处理方式。</td>
    </tr>
     <tr>
            <td>
            <figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">sequenceOf(<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>)</span><br><span class="line">    .filter &#123; </span><br><span class="line">        print(<span class="string">&quot;F<span class="variable">$it</span>, &quot;</span>); </span><br><span class="line">        it % <span class="number">2</span> == <span class="number">1</span> </span><br><span class="line">    &#125;</span><br><span class="line">    .map &#123; </span><br><span class="line">        print(<span class="string">&quot;M<span class="variable">$it</span>, &quot;</span>); </span><br><span class="line">        it * <span class="number">2</span> </span><br><span class="line">    &#125;</span><br><span class="line">    .forEach &#123; </span><br><span class="line">        print(<span class="string">&quot;E<span class="variable">$it</span>, &quot;</span>) </span><br><span class="line">    &#125;</span><br><span class="line"><span class="comment">// Prints: F1, M1, E2, F2, F3, M3, E6, </span></span><br></pre></td></tr></table></figure>
            </td>
            <td>
            <figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">listOf(<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>)</span><br><span class="line">    .filter &#123; </span><br><span class="line">        print(<span class="string">&quot;F<span class="variable">$it</span>, &quot;</span>); </span><br><span class="line">        it % <span class="number">2</span> == <span class="number">1</span> </span><br><span class="line">    &#125;</span><br><span class="line">    .map &#123; </span><br><span class="line">        print(<span class="string">&quot;M<span class="variable">$it</span>, &quot;</span>); </span><br><span class="line">        it * <span class="number">2</span> </span><br><span class="line">    &#125;</span><br><span class="line">    .forEach &#123; </span><br><span class="line">        print(<span class="string">&quot;E<span class="variable">$it</span>, &quot;</span>) </span><br><span class="line">    &#125;</span><br><span class="line"><span class="comment">// Prints: F1, F2, F3, M1, M3, E2, E6,</span></span><br></pre></td></tr></table></figure>
            </td>
        </tr>
</table>


<center>
    <img src="../images/kotlin_sequence_order.jpeg" width="500"/>
</center>

<p>如果我们不用集合处理函数，而是用循环和条件语句，这和sequence一样，也是一种元素接元素的处理方式。这也为我们提供了一种编译器底层优化的思路：sequence操作可以被优化成循环和条件。</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> (e <span class="keyword">in</span> listOf(<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>)) &#123;</span><br><span class="line">    print(<span class="string">&quot;F<span class="variable">$e</span>, &quot;</span>)</span><br><span class="line">    <span class="keyword">if</span> (e % <span class="number">2</span> == <span class="number">1</span>) &#123;</span><br><span class="line">        print(<span class="string">&quot;M<span class="variable">$e</span>, &quot;</span>)</span><br><span class="line">        <span class="keyword">val</span> mapped = e * <span class="number">2</span></span><br><span class="line">        print(<span class="string">&quot;E<span class="variable">$mapped</span>, &quot;</span>)</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// Prints: F1, M1, E2, F2, F3, M3, E6,</span></span><br></pre></td></tr></table></figure>


<h5 id="二、Sequence执行最少的操作"><a href="#二、Sequence执行最少的操作" class="headerlink" title="二、Sequence执行最少的操作"></a>二、Sequence执行最少的操作</h5><p>我们没必要每一步都处理整个集合。假如我们有一百万个数据，我们只需要前十个，没必要处理十个之后的数据。所以sequence可以执行最少的操作。</p>
<center>
    <img src="../images/kotlin_sequence_min_op.jpeg" width="500"/>
</center>

<p>看下面的例子：</p>
<table>
     <tr>
            <td>
            <figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">(<span class="number">1.</span><span class="number">.10</span>).asSequence()</span><br><span class="line">    .filter &#123; </span><br><span class="line">        print(<span class="string">&quot;F<span class="variable">$it</span>, &quot;</span>); </span><br><span class="line">        it % <span class="number">2</span> == <span class="number">1</span> </span><br><span class="line">    &#125;</span><br><span class="line">    .map &#123; </span><br><span class="line">        print(<span class="string">&quot;M<span class="variable">$it</span>, &quot;</span>); </span><br><span class="line">        it * <span class="number">2</span> </span><br><span class="line">    &#125;</span><br><span class="line">    .find &#123; </span><br><span class="line">        it &gt; <span class="number">5</span> </span><br><span class="line">    &#125;</span><br><span class="line"><span class="comment">// Prints: F1, M1, F2, F3, M3,</span></span><br></pre></td></tr></table></figure>
            </td>
            <td>
            <figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">(<span class="number">1.</span><span class="number">.10</span>)</span><br><span class="line">    .filter &#123; </span><br><span class="line">        print(<span class="string">&quot;F<span class="variable">$it</span>, &quot;</span>); </span><br><span class="line">        it % <span class="number">2</span> == <span class="number">1</span> </span><br><span class="line">    &#125;</span><br><span class="line">    .map &#123; </span><br><span class="line">        print(<span class="string">&quot;M<span class="variable">$it</span>, &quot;</span>); </span><br><span class="line">        it * <span class="number">2</span> </span><br><span class="line">    &#125;</span><br><span class="line">    .find &#123; </span><br><span class="line">        it &gt; <span class="number">5</span> </span><br><span class="line">    &#125;</span><br><span class="line"><span class="comment">// Prints: </span></span><br><span class="line"><span class="comment">//F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, </span></span><br><span class="line"><span class="comment">// M1, M3, M5, M7, M9,         </span></span><br></pre></td></tr></table></figure>
            </td>
        </tr>
</table>

<p>这个例子中，有很多个操作符，最后的终止操作符不需要处理所有的数据，因此sequence性能更好。类似的操作符还有：<code>first</code>, <code>find</code>, <code>take</code>, <code>any</code>, <code>all</code>, <code>none</code> 或 <code>indexOf</code>。</p>
<h5 id="三、Sequence是无限的"><a href="#三、Sequence是无限的" class="headerlink" title="三、Sequence是无限的"></a>三、Sequence是无限的</h5><p>由于Sequence按需处理，我们可以定义无限序列。一种常用的方式是使用sequence生成器 <code>generateSequence</code> 或 <code>sequence</code> 。</p>
<p><code>generateSequence</code>需要传如第一个值，以及如何产生下一个值：</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">generateSequence(<span class="number">1</span>) &#123; it + <span class="number">1</span> &#125;</span><br><span class="line">    .map &#123; it * <span class="number">2</span> &#125;</span><br><span class="line">    .take(<span class="number">10</span>)</span><br><span class="line">    .forEach &#123; print(<span class="string">&quot;<span class="variable">$it</span>, &quot;</span>) &#125;</span><br><span class="line"><span class="comment">// Prints: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20,</span></span><br></pre></td></tr></table></figure>

<p><code>sequence</code> 则使用挂起函数按需生成数据。只要我们需要数据他就执行，一直到调用yield方法。然后挂起直到下次再向他请求数据。下面是一个无限生成斐波那契数列的例子：</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.math.BigDecimal</span><br><span class="line"></span><br><span class="line"><span class="keyword">val</span> fibonacci: Sequence&lt;BigDecimal&gt; = sequence &#123;</span><br><span class="line">    <span class="keyword">var</span> current = <span class="number">1.</span>toBigDecimal()</span><br><span class="line">    <span class="keyword">var</span> prev = <span class="number">1.</span>toBigDecimal()</span><br><span class="line">    yield(prev)</span><br><span class="line">    <span class="keyword">while</span> (<span class="literal">true</span>) &#123;</span><br><span class="line">        yield(current)</span><br><span class="line">        <span class="keyword">val</span> temp = prev</span><br><span class="line">        prev = current</span><br><span class="line">        current += temp</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">main</span><span class="params">()</span></span> &#123;</span><br><span class="line">    print(fibonacci.take(<span class="number">10</span>).toList())</span><br><span class="line">    <span class="comment">// [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>需要注意的是，使用无限序列需要限制元素的数量，否则将无限的运行下去。</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">print(fibonacci.toList()) <span class="comment">// Runs forever</span></span><br></pre></td></tr></table></figure>

<p>为了不让它无限循环的运行，我们可以使用<code>take</code>限制元素数量，或者使用first、find、indexOf等。在不限制数量的情况下，不要使用any、all、none。</p>
<h5 id="四、sequence每一步不产生新集合"><a href="#四、sequence每一步不产生新集合" class="headerlink" title="四、sequence每一步不产生新集合"></a>四、sequence每一步不产生新集合</h5><p>标准的集合处理函数每一步都返回新的集合，当我们处理大量数据时会分配很多临时内存。</p>
<table>
     <tr>
         <td>
            <figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">num</span><br><span class="line">   .filter &#123;<span class="comment">// 1                   </span></span><br><span class="line">       it % <span class="number">10</span> == <span class="number">0</span> </span><br><span class="line">   &#125; </span><br><span class="line">   .map &#123;<span class="comment">// 2      </span></span><br><span class="line">       it * <span class="number">2</span> </span><br><span class="line">   &#125; </span><br><span class="line">   .sum()</span><br><span class="line"><span class="comment">// In total, 2 collections </span></span><br><span class="line"><span class="comment">// created under the hood</span></span><br></pre></td></tr></table></figure>
         </td>
         <td>
            <figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">num.asSequence()</span><br><span class="line">   .filter &#123;<span class="comment">//0 </span></span><br><span class="line">      it % <span class="number">10</span> == <span class="number">0</span> </span><br><span class="line">   &#125;</span><br><span class="line">   .map &#123;<span class="comment">//0</span></span><br><span class="line">      it * <span class="number">2</span> </span><br><span class="line">   &#125;</span><br><span class="line">   .sum()</span><br><span class="line"><span class="comment">// No collections created</span></span><br></pre></td></tr></table></figure>
         </td>
     </tr>
</table>

<p>一个极端又常见的例子：文件读取。文件可能是几个G，每执行一个操作符都分配这么多内存是一种极大的浪费。下面例子是读取大小1.53G的芝加哥犯罪记录中包含毒品交易信息的记录数量，其中readLines 返回 List<String>。</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// BAD SOLUTION, DO NOT USE COLLECTIONS FOR </span></span><br><span class="line"><span class="comment">// POSSIBLY BIG FILES</span></span><br><span class="line">File(<span class="string">&quot;ChicagoCrimes.csv&quot;</span>)</span><br><span class="line">    .readLines()</span><br><span class="line">    .drop(<span class="number">1</span>) <span class="comment">// Drop descriptions of the columns</span></span><br><span class="line">    .mapNotNull &#123; it.split(<span class="string">&quot;,&quot;</span>).getOrNull(<span class="number">6</span>) &#125;</span><br><span class="line">    <span class="comment">// Find description</span></span><br><span class="line">    .filter &#123; <span class="string">&quot;CANNABIS&quot;</span> <span class="keyword">in</span> it &#125;</span><br><span class="line">    .count()</span><br><span class="line">    .let(::println)</span><br></pre></td></tr></table></figure>
<p>这段程序在我电脑上的运行结果是：</p>
<figure class="highlight shell"><figcaption><span>script</span></figcaption><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">OutOfMemoryError.n&gt; Exception in thread &quot;main&quot; java.lang.OutOfMemoryError: Java heap space</span><br></pre></td></tr></table></figure>

<p>我们创建了一个集合，中间三个操作符产生集合，一个四个集合。其中三个包含文件的主要主要数据记录，一共消耗4.59G。正确的实现应该使用sequence，我们使用<code>useLines</code>函数，每次只操作一行记录。</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">File(<span class="string">&quot;ChicagoCrimes.csv&quot;</span>).useLines &#123; lines -&gt;</span><br><span class="line"><span class="comment">// The type of `lines` is Sequence&lt;String&gt;</span></span><br><span class="line">    lines.drop(<span class="number">1</span>) <span class="comment">// Drop descriptions of the columns</span></span><br><span class="line">        .mapNotNull &#123; it.split(<span class="string">&quot;,&quot;</span>).getOrNull(<span class="number">6</span>) &#125;</span><br><span class="line">        <span class="comment">// Find description</span></span><br><span class="line">        .filter &#123; <span class="string">&quot;CANNABIS&quot;</span> <span class="keyword">in</span> it &#125;</span><br><span class="line">        .count()</span><br><span class="line">        .let &#123; println(it) &#125; <span class="comment">// 318185</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>同样运行这段代码，只耗时8.3s。为了比较一下这两种方法的效率，我做了另外一个实验：删除数据中不必要的列以减少文件大小，得到<code>CrimeData.csv</code>只有728MB，然后做相同的操作。使用Collection处理函数，耗时13s，使用sequence函数，耗时4.5s。正如实验数据，使用sequence处理大文件不仅节约内存，而且提升性能。</p>
<p>事实上，在每个步骤中，我们创建一个新的集合本身也是一种成本，当我们处理包含大量元素的集合时，这种成本就会显现出来。差别并不大——主要是因为在许多步骤中创建的集合都是用预期的大小初始化的，所以当我们添加元素时，我们只需要将它们放在下一个位置。尽管即使是廉价的集合复制也比完全不复制要昂贵，这也是为什么我们应该更喜欢对具有<em>多个处理步骤</em>的<em>大集合</em>使用Sequence的主要原因。</p>
<blockquote>
<p>大集合：元素多（含数万个元素的整数列表）、元素大（超长字符串）</p>
<p>多个处理步骤：处理集合时使用很多操作符。</p>
</blockquote>
<p>如果对比下面两个函数：</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">singleStepListProcessing</span><span class="params">()</span></span>: List&lt;Product&gt; &#123;</span><br><span class="line">    <span class="keyword">return</span> productsList.filter &#123; it.bought &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">singleStepSequenceProcessing</span><span class="params">()</span></span>: List&lt;Product&gt; &#123;</span><br><span class="line">    <span class="keyword">return</span> productsList.asSequence()</span><br><span class="line">        .filter &#123; it.bought &#125;</span><br><span class="line">        .toList()</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>你会发现，在性能上区别不大（实际上，简单的list处理更快，因为它的filter函数是内联的）。但是，当你使用多个操作符，先filter再map，在大集合上性能问题就行显现出来。为了看到区别，我们比较一下2个操作符和3个操作符处理5000个数据的情况：</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">twoStepListProcessing</span><span class="params">()</span></span>: List&lt;<span class="built_in">Double</span>&gt; &#123;</span><br><span class="line">    <span class="keyword">return</span> productsList</span><br><span class="line">        .filter &#123; it.bought &#125;</span><br><span class="line">        .map &#123; it.price &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">twoStepSequenceProcessing</span><span class="params">()</span></span>: List&lt;<span class="built_in">Double</span>&gt; &#123;</span><br><span class="line">    <span class="keyword">return</span> productsList.asSequence()</span><br><span class="line">        .filter &#123; it.bought &#125;</span><br><span class="line">        .map &#123; it.price &#125;</span><br><span class="line">        .toList()</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">threeStepListProcessing</span><span class="params">()</span></span>: <span class="built_in">Double</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> productsList</span><br><span class="line">        .filter &#123; it.bought &#125;</span><br><span class="line">        .map &#123; it.price &#125;</span><br><span class="line">        .average()</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">threeStepSequenceProcessing</span><span class="params">()</span></span>: <span class="built_in">Double</span> &#123;</span><br><span class="line">    <span class="keyword">return</span> productsList.asSequence()</span><br><span class="line">        .filter &#123; it.bought &#125;</span><br><span class="line">        .map &#123; it.price &#125;</span><br><span class="line">        .average()</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>下面是在MacBook Pro(Retina, 15-inch, Late 2013)处理5000个元素的平均结果：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">twoStepListProcessing                        81 095 ns</span><br><span class="line">twoStepSequenceProcessing                    55 685 ns</span><br><span class="line">twoStepListProcessingAndAcumulate            83 307 ns</span><br><span class="line">twoStepSequenceProcessingAndAcumulate         6 928 ns</span><br></pre></td></tr></table></figure>

<p>很难预测我们能提升但是性能，根据我的观察，在一个包含多个步骤的典型集合处理中，对于至少几千个元素，我们可以预期大约20-40%的性能提升。</p>
<h5 id="五、sequence什么时候没那么快？"><a href="#五、sequence什么时候没那么快？" class="headerlink" title="五、sequence什么时候没那么快？"></a>五、sequence什么时候没那么快？</h5><p>有些情况我们要处理整个集合，sequence并不能给我们带来什么收益。如<code>sorted</code>（当前来讲它是唯一一个例子）。sorted的最优实现：积攒Sequence并放入List，然后使用Java的sort函数。缺点是，与<code>Collection.sort</code>相比，积攒过程会消耗额外的时间。</p>
<p>Sequence是否应该支持<code>sorted</code>函数是有争议的，因为当一个序列的方法需要所有元素才能完成计算时，后续操作只是部分延迟，并且它不支持无限序列。之所以添加sorted操作只是因为它很常用，好用。Kotlin开发者需要了解它的缺陷，尤其是它不能用于无限序列。</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">generateSequence(<span class="number">0</span>) &#123; it + <span class="number">1</span> &#125;.take(<span class="number">10</span>).sorted().toList()</span><br><span class="line"><span class="comment">// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</span></span><br><span class="line">generateSequence(<span class="number">0</span>) &#123; it + <span class="number">1</span> &#125;.sorted().take(<span class="number">10</span>).toList()</span><br><span class="line"><span class="comment">// Infinite time. Does not return.</span></span><br></pre></td></tr></table></figure>

<p>在Collection上使用sorted比在Sequence上更快只是少数特例。当我们只使用很少操作符函数和单个sorted函数时，还是建议使用sequence来处理。</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">productsList.asSequence()</span><br><span class="line">    .filter &#123; it.bought &#125;</span><br><span class="line">    .map &#123; it.price &#125;</span><br><span class="line">    .sorted()</span><br><span class="line">    .take(<span class="number">10</span>)</span><br><span class="line">    .sum()</span><br></pre></td></tr></table></figure>

<h5 id="六、看看Java的Stream操作"><a href="#六、看看Java的Stream操作" class="headerlink" title="六、看看Java的Stream操作"></a>六、看看Java的Stream操作</h5><p>Java 8新增了集合处理流的特性，看起来和Kotlin的序列很像。</p>
<table>
     <tr>
         <td>
            <figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">productsList.asSequence()</span><br><span class="line">    .filter &#123; it.bought &#125;</span><br><span class="line">    .map &#123; it.price &#125;</span><br><span class="line">    .average()</span><br></pre></td></tr></table></figure>
         </td>
         <td>
            <figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">productsList.stream()</span><br><span class="line">    .filter &#123; it.bought &#125;</span><br><span class="line">    .mapToDouble &#123; it.price &#125;</span><br><span class="line">    .average()</span><br><span class="line">    .orElse(<span class="number">0.0</span>)</span><br></pre></td></tr></table></figure>
         </td>
     </tr>
</table>

<p>Java 8的Stream也是惰性的在最后一个操作符触发计算。与Kotlin sequence的区别主要是：</p>
<ul>
<li>Kotlin sequence包含更多的处理函数（被定义为拓展函数），使用简单: <code>toList()</code> vs <code>collect(Collectors.toList())</code></li>
<li>Java stream可以开启并行模式，在多核处理器上会有很大的性能提升。</li>
<li>Kotlin sequence可以用于Kotlin/JVM、Kotlin/JS、Kotlin/Native模块中。Java stream只能用于Kotlin/JVM，且JVM版本至少是8</li>
</ul>
<p>总之，我们不用Java stream并行模式时很难将谁的性能更好，我建议少用Java stream，只有在处理重量级计算问题中使用并行模式可以显著带来收益的情况下使用，其他情况用Kotlin标准函数能带来清晰的代码结构和多平台支持。</p>
<h5 id="七、调试Sequence"><a href="#七、调试Sequence" class="headerlink" title="七、调试Sequence"></a>七、调试Sequence</h5><p>Kotlin Sequence和Java Stream都支持debug每一步操作。Java需要使用”Java Stream Debugger”插件，Kotlin则需要”Kotlin Sequence Debugger”插件，现在已经被集成在了Kotlin插件中了。</p>
<center>
    <img src="../images/kotlin_sequence_debug.jpeg" width="500"/>
</center>


<h4 id="三、总结"><a href="#三、总结" class="headerlink" title="三、总结"></a>三、总结</h4><p>集合和序列非常相似，都支持相同的处理函数。但他们也有很大的区别。Sequence处理是困难的，因为我们要保持原集合不变，执行相应转换后再放回原集合。Sequence是惰性的，带来很多优点：</p>
<ul>
<li>保证操作的顺序性</li>
<li>保证操作执行次数最少化</li>
<li>他们可以是无限的</li>
<li>无需每一步创建新的集合</li>
</ul>
<p>基于这些优点，对于包含多个处理步骤的包含大对象或元素很多的集合来说使用Sequence更好。Sequence也包含调试器，能帮助我们可视化的分析元素处理过程。Sequence不是为了取代传统的集合处理方式，使用前应该分析清楚自己的目的和原因才能带来性能的提升以及更少的内存问题。</p>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://wangduwei.top/kotlin-coroutine-deep-recursion.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpeg">
      <meta itemprop="name" content="wangduwei">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="嗅不到北的狗子">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/kotlin-coroutine-deep-recursion.html" class="post-title-link" itemprop="url">用Kotlin协程解决深度递归问题</a>
        </h2>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>
              

              <time title="创建时间：2021-10-30 10:38:30 / 修改时间：15:07:42" itemprop="dateCreated datePublished" datetime="2021-10-30T10:38:30+08:00">2021-10-30</time>
            </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/Kotlin/" itemprop="url" rel="index"><span itemprop="name">Kotlin</span></a>
                </span>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/kotlin-coroutine-deep-recursion.html#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/kotlin-coroutine-deep-recursion.html" itemprop="commentCount"></span>
    </a>
  </span>
  
  <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="far fa-file-word"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>3.1k</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="far fa-clock"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>3 分钟</span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <p>&ensp;&ensp;&ensp;&ensp;协程一般用于异步编程。在解决异步编程问题方面，Kotlin编译器在对协程的设计和实现是通用的。我们可以借助协程优雅的解决深度递归问题。</p>
<h4 id="一、问题描述"><a href="#一、问题描述" class="headerlink" title="一、问题描述"></a>一、问题描述</h4><p>定义以下二叉树的结点，并构造一棵只含十万个左结点的树，进行深度遍历，求树的深度：  </p>
<center>
    <img src="../images/tree_only_left.png" width="500"/>
</center>

<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//结点定义</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Tree</span></span>(<span class="keyword">val</span> left: Tree?, <span class="keyword">val</span> right: Tree?)</span><br><span class="line"></span><br><span class="line"><span class="comment">//构造二叉树：以叶子结点开始，重复构造父结点，并把当前结点作为父结点的左子树</span></span><br><span class="line"><span class="keyword">val</span> n = <span class="number">100_000</span></span><br><span class="line"><span class="keyword">val</span> deepTree = generateSequence(Tree(<span class="literal">null</span>, <span class="literal">null</span>)) &#123; prev -&gt;</span><br><span class="line">    Tree(prev, <span class="literal">null</span>) </span><br><span class="line">&#125;.take(n).last()</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h4 id="二、解决方案"><a href="#二、解决方案" class="headerlink" title="二、解决方案"></a>二、解决方案</h4><h5 id="2-1-解决方案一："><a href="#2-1-解决方案一：" class="headerlink" title="2.1 解决方案一："></a>2.1 解决方案一：</h5><figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">depth</span><span class="params">(t: <span class="type">Tree</span>?)</span></span>: <span class="built_in">Int</span> =</span><br><span class="line">    <span class="keyword">if</span> (t == <span class="literal">null</span>) <span class="number">0</span> <span class="keyword">else</span> maxOf(</span><br><span class="line">        depth(t.left), <span class="comment">// recursive call one</span></span><br><span class="line">        depth(t.right) <span class="comment">// recursive call two</span></span><br><span class="line">    ) + <span class="number">1</span></span><br></pre></td></tr></table></figure>

<p>分析：<br>对树进行递归是最简洁直接的解决方案。而递归将保存函数的调用栈用于后续状态恢复，线程的调用栈是有大小限制的，此处将抛出<code>Exception in thread &quot;main&quot; java.lang.StackOverflowError</code>错误。</p>
<h5 id="2-2-解决方案二："><a href="#2-2-解决方案二：" class="headerlink" title="2.2 解决方案二："></a>2.2 解决方案二：</h5><figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">depth</span><span class="params">(t: <span class="type">Tree</span>?)</span></span>: <span class="built_in">Int</span> &#123;</span><br><span class="line">      <span class="keyword">if</span> (t == <span class="literal">null</span>) <span class="keyword">return</span> <span class="number">0</span></span><br><span class="line">      <span class="class"><span class="keyword">class</span> <span class="title">Frame</span></span>(<span class="keyword">val</span> node: Tree, <span class="keyword">var</span> state: <span class="built_in">Int</span> = <span class="number">0</span>, <span class="keyword">var</span> depth: <span class="built_in">Int</span> = <span class="number">1</span>)</span><br><span class="line">      <span class="keyword">val</span> stack = ArrayList&lt;Frame&gt;()</span><br><span class="line">      <span class="keyword">val</span> root = Frame(t)</span><br><span class="line">      stack.add(root)</span><br><span class="line">      <span class="keyword">while</span> (stack.isNotEmpty()) &#123;</span><br><span class="line">          <span class="keyword">val</span> frame = stack.last()</span><br><span class="line">          <span class="keyword">when</span> (frame.state++) &#123;</span><br><span class="line">              <span class="number">0</span> -&gt; frame.node.left?.let &#123; l -&gt; stack.add(Frame(l)) &#125;</span><br><span class="line">              <span class="number">1</span> -&gt; frame.node.right?.let &#123; r -&gt; stack.add(Frame(r)) &#125;</span><br><span class="line">              <span class="number">2</span> -&gt; &#123;</span><br><span class="line">                  stack.removeLast()</span><br><span class="line">                  stack.lastOrNull()?.let &#123; p -&gt; </span><br><span class="line">                      p.depth = maxOf(p.depth, frame.depth + <span class="number">1</span>) </span><br><span class="line">                  &#125;</span><br><span class="line">              &#125;</span><br><span class="line">          &#125;</span><br><span class="line">      &#125;</span><br><span class="line">      <span class="keyword">return</span> root.depth</span><br><span class="line">  &#125;</span><br></pre></td></tr></table></figure>
<p>分析：<br>基于解决方案一，我们考虑将调用栈状态的保存转移到内存空间更大的堆区，并加入了状态机和<code>while</code>循环。在此例中，程序开始时将全部走状态0，将所有的左节点加入stack。然后全部走状态2(因为没有右结点)，由下到上计算每一个结点的深度。最后返回根节点的深度。</p>
<h5 id="2-3-解决方案三："><a href="#2-3-解决方案三：" class="headerlink" title="2.3 解决方案三："></a>2.3 解决方案三：</h5><figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">val</span> depth = DeepRecursiveFunction&lt;Tree?, <span class="built_in">Int</span>&gt; &#123; t -&gt;</span><br><span class="line">        <span class="keyword">if</span> (t == <span class="literal">null</span>) <span class="number">0</span> <span class="keyword">else</span> maxOf(</span><br><span class="line">            callRecursive(t.left),</span><br><span class="line">            callRecursive(t.right)</span><br><span class="line">        ) + <span class="number">1</span></span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>

<p>分析：<br>方案二中的状态机就是Kotlin挂起函数的实现原理。所以我们也可以利用Kotlin的挂起函数实现深度遍历。那么方案三是如何实现的呢？我们分析三个方面：  </p>
<ul>
<li>如何调用</li>
<li>如何进入循环</li>
<li>如何保存状态</li>
</ul>
<p>2.3.1 调用<br><code>DeepRecursiveFunction</code>类声明了<code>invoke</code>操作符，调用<code>depth</code>函数就是调用下面👇🏻的操作符。</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">@SinceKotlin(<span class="meta-string">&quot;1.4&quot;</span>)</span></span><br><span class="line"><span class="meta">@ExperimentalStdlibApi</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">operator</span> <span class="function"><span class="keyword">fun</span> <span class="type">&lt;T, R&gt;</span> DeepRecursiveFunction<span class="type">&lt;T, R&gt;</span>.<span class="title">invoke</span><span class="params">(value: <span class="type">T</span>)</span></span>: R =</span><br><span class="line">    DeepRecursiveScopeImpl&lt;T, R&gt;(block, value).runCallLoop()</span><br></pre></td></tr></table></figure>

<p>2.3.2 循环<br>调用<code>DeepRecursiveFunction</code>后直接进入<code>runCallLoop()</code>循环，result的默认值为UNDEFINED_RESULT，所以会启动我们的递归业务逻辑</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">@Suppress(<span class="meta-string">&quot;UNCHECKED_CAST&quot;</span>)</span></span><br><span class="line">   <span class="function"><span class="keyword">fun</span> <span class="title">runCallLoop</span><span class="params">()</span></span>: R &#123;</span><br><span class="line">       <span class="keyword">while</span> (<span class="literal">true</span>) &#123;</span><br><span class="line">           <span class="comment">// Note: cont is set to null in DeepRecursiveScopeImpl.resumeWith when the whole computation completes</span></span><br><span class="line">           <span class="keyword">val</span> result = <span class="keyword">this</span>.result</span><br><span class="line">           <span class="keyword">val</span> cont = <span class="keyword">this</span>.cont</span><br><span class="line">               ?: <span class="keyword">return</span> (result <span class="keyword">as</span> Result&lt;R&gt;).getOrThrow() <span class="comment">// done -- final result</span></span><br><span class="line">           <span class="comment">// The order of comparison is important here for that case of rogue class with broken equals</span></span><br><span class="line">           <span class="keyword">if</span> (UNDEFINED_RESULT == result) &#123;</span><br><span class="line">               <span class="comment">// call &quot;function&quot; with &quot;value&quot; using &quot;cont&quot; as completion</span></span><br><span class="line">               <span class="keyword">val</span> r = <span class="keyword">try</span> &#123;</span><br><span class="line">                   <span class="comment">// This is block.startCoroutine(this, value, cont)</span></span><br><span class="line">                   function.startCoroutineUninterceptedOrReturn(<span class="keyword">this</span>, value, cont)</span><br><span class="line">               &#125; <span class="keyword">catch</span> (e: Throwable) &#123;</span><br><span class="line">                   cont.resumeWithException(e)</span><br><span class="line">                   <span class="keyword">continue</span></span><br><span class="line">               &#125;</span><br><span class="line">               <span class="comment">// If the function returns without suspension -- calls its continuation immediately</span></span><br><span class="line">               <span class="keyword">if</span> (r !== COROUTINE_SUSPENDED)</span><br><span class="line">                   cont.resume(r <span class="keyword">as</span> R)</span><br><span class="line">           &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">               <span class="comment">// we returned from a crossFunctionCompletion trampoline -- call resume here</span></span><br><span class="line">               <span class="keyword">this</span>.result = UNDEFINED_RESULT <span class="comment">// reset result back</span></span><br><span class="line">               cont.resumeWith(result)</span><br><span class="line">           &#125;</span><br><span class="line">       &#125;</span><br><span class="line">   &#125;</span><br></pre></td></tr></table></figure>


<p>2.3.3 状态保存<br>每次调用<code>callRecursive</code>时将保存当前的值和cont（continuation），注意这里cont对象每次都不是同一个对象。当进行挂起恢复时，拿到旧的continuation进行回调。</p>
<center>
    <img src="../images/kotlin_coroutine_resume.jpeg" width="500"/>
</center>

<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">suspend</span> <span class="function"><span class="keyword">fun</span> <span class="title">callRecursive</span><span class="params">(value: <span class="type">T</span>)</span></span>: R = </span><br><span class="line">    suspendCoroutineUninterceptedOrReturn &#123; cont -&gt;</span><br><span class="line">        <span class="keyword">this</span>.cont = cont</span><br><span class="line">        <span class="keyword">this</span>.value = value</span><br><span class="line">        COROUTINE_SUSPENDED</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>


<h4 id="参考："><a href="#参考：" class="headerlink" title="参考："></a>参考：</h4><p><a target="_blank" rel="noopener" href="https://elizarov.medium.com/deep-recursion-with-coroutines-7c53e15993e3">Deep recursion with coroutines</a></p>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://wangduwei.top/android-basic-constraintlayout.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpeg">
      <meta itemprop="name" content="wangduwei">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="嗅不到北的狗子">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/android-basic-constraintlayout.html" class="post-title-link" itemprop="url">Android中的约束布局</a>
        </h2>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2021-10-23 15:03:23" itemprop="dateCreated datePublished" datetime="2021-10-23T15:03:23+08:00">2021-10-23</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2021-10-25 09:31:28" itemprop="dateModified" datetime="2021-10-25T09:31:28+08:00">2021-10-25</time>
              </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/Android/" itemprop="url" rel="index"><span itemprop="name">Android</span></a>
                </span>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/android-basic-constraintlayout.html#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/android-basic-constraintlayout.html" itemprop="commentCount"></span>
    </a>
  </span>
  
  <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="far fa-file-word"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>5k</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="far fa-clock"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>5 分钟</span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h4 id="一、概述"><a href="#一、概述" class="headerlink" title="一、概述"></a>一、概述</h4><p>&ensp;&ensp;&ensp;&ensp;Android中的视图是以树的形式组织起来的，它是一种层次结构。在代码中体现为组合模式，一个ViewGroup可以包含一个或多个View，同时ViewGroup又是一个View。在布局文件中体现为xml的结点和缩进。<br>&ensp;&ensp;&ensp;&ensp;同时视图的渲染少不了对其进行遍历，这就涉及数据结构中树的深度优先遍历和广度优先遍历。有时候一些复杂的布局一次遍历还无法完全确定View的信息。如何通过算法方式降低树的层次呢？也许这就是约束布局存在的意义吧。<br>&ensp;&ensp;&ensp;&ensp;在Android中，灵活运用ConstraintLayout包括以下几个点：</p>
<ul>
<li>主属性<ul>
<li>通过相对位置约束View</li>
<li>控制约束之间的距离</li>
<li>居中和偏移百分比</li>
<li>通过圆定位📌View</li>
<li>通过可见性控制View</li>
<li>通过分辨率约束View</li>
<li>通过链⛓约束View</li>
</ul>
</li>
<li>辅助工具<ul>
<li>Barrier屏障约束</li>
<li>Group分组约束</li>
<li>Placeholder占位约束</li>
<li>Guideline引导线约束</li>
</ul>
</li>
</ul>
<h4 id="二、使用"><a href="#二、使用" class="headerlink" title="二、使用"></a>二、使用</h4><h5 id="2-1-通过相对位置约束View"><a href="#2-1-通过相对位置约束View" class="headerlink" title="2.1 通过相对位置约束View"></a>2.1 通过相对位置约束View</h5><center>
    <img src="../images/constraint/constraint_relative_position.png" width="500"/>
</center>

<table>
<thead>
<tr>
<th>约束属性</th>
<th>描述</th>
<th>约束属性</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>layout_constraintLeft_toLeftOf</td>
<td></td>
<td>layout_constraintLeft_toRightOf</td>
<td></td>
</tr>
<tr>
<td>layout_constraintRight_toLeftOf</td>
<td></td>
<td>layout_constraintRight_toRightOf</td>
<td></td>
</tr>
<tr>
<td>layout_constraintTop_toTopOf</td>
<td></td>
<td>layout_constraintTop_toBottomOf</td>
<td></td>
</tr>
<tr>
<td>layout_constraintBottom_toTopOf</td>
<td></td>
<td>layout_constraintBottom_toBottomOf</td>
<td></td>
</tr>
<tr>
<td>layout_constraintStart_toEndOf</td>
<td></td>
<td>layout_constraintStart_toStartOf</td>
<td></td>
</tr>
<tr>
<td>layout_constraintEnd_toStartOf</td>
<td></td>
<td>layout_constraintEnd_toEndOf</td>
<td></td>
</tr>
<tr>
<td>layout_constraintBaseline_toBaselineOf</td>
<td></td>
<td></td>
<td></td>
</tr>
</tbody></table>
<h5 id="2-2-控制约束之间的距离"><a href="#2-2-控制约束之间的距离" class="headerlink" title="2.2 控制约束之间的距离"></a>2.2 控制约束之间的距离</h5><center>
    <img src="../images/constraint/constraint_margin.png" width="500"/>
</center> 

<table>
<thead>
<tr>
<th>约束属性</th>
<th>描述</th>
<th>约束属性</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>android:layout_marginStart</td>
<td></td>
<td>layout_goneMarginStart</td>
<td></td>
</tr>
<tr>
<td>android:layout_marginEnd</td>
<td></td>
<td>layout_goneMarginEnd</td>
<td></td>
</tr>
<tr>
<td>android:layout_marginLeft</td>
<td></td>
<td>layout_goneMarginLeft</td>
<td></td>
</tr>
<tr>
<td>android:layout_marginTop</td>
<td></td>
<td>layout_goneMarginTop</td>
<td></td>
</tr>
<tr>
<td>android:layout_marginRight</td>
<td></td>
<td>layout_goneMarginRight</td>
<td></td>
</tr>
<tr>
<td>android:layout_marginBottom</td>
<td></td>
<td>layout_goneMarginBottom</td>
<td></td>
</tr>
<tr>
<td>android:layout_marginBaseline</td>
<td></td>
<td>layout_goneMarginBaseline</td>
<td></td>
</tr>
</tbody></table>
<h5 id="2-3-居中和偏移百分比"><a href="#2-3-居中和偏移百分比" class="headerlink" title="2.3 居中和偏移百分比"></a>2.3 居中和偏移百分比</h5><table>
    <tr>
        <td><img src="../images/constraint/constraint_center_position.png" width="300"/></td>
        <td><img src="../images/constraint/constraint_center_position_bias.png" width="300"/></td>
    </tr>
</table>

<table>
<thead>
<tr>
<th>约束属性</th>
<th>描述</th>
<th>约束属性</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>layout_constraintHorizontal_bias</td>
<td></td>
<td>layout_constraintVertical_bias</td>
<td></td>
</tr>
</tbody></table>
<h5 id="2-4-通过圆定位📌View"><a href="#2-4-通过圆定位📌View" class="headerlink" title="2.4 通过圆定位📌View"></a>2.4 通过圆定位📌View</h5><center>
    <img src="../images/constraint/constraint_circular_position.jpeg" width="400"/>
</center>

<table>
<thead>
<tr>
<th>约束属性</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>layout_constraintCircle</td>
<td>另一个widget的id</td>
</tr>
<tr>
<td>layout_constraintCircleRadius</td>
<td>圆的半径</td>
</tr>
<tr>
<td>layout_constraintCircleAngle</td>
<td>角度</td>
</tr>
</tbody></table>
<figure class="highlight xml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="tag">&lt;<span class="name">Button</span> <span class="attr">android:id</span>=<span class="string">&quot;@+id/buttonB&quot;</span> </span></span><br><span class="line"><span class="tag">   <span class="attr">app:layout_constraintCircle</span>=<span class="string">&quot;@+id/buttonA&quot;</span></span></span><br><span class="line"><span class="tag">   <span class="attr">app:layout_constraintCircleRadius</span>=<span class="string">&quot;100dp&quot;</span></span></span><br><span class="line"><span class="tag">   <span class="attr">app:layout_constraintCircleAngle</span>=<span class="string">&quot;45&quot;</span> /&gt;</span></span><br></pre></td></tr></table></figure>

<h5 id="2-5-通过可见性控制View"><a href="#2-5-通过可见性控制View" class="headerlink" title="2.5 通过可见性控制View"></a>2.5 通过可见性控制View</h5><center>
    <img src="../images/constraint/constraint_visibility_behavior.jpeg" width="400"/>
</center>

<h5 id="2-6-通过分辨率约束View"><a href="#2-6-通过分辨率约束View" class="headerlink" title="2.6 通过分辨率约束View"></a>2.6 通过分辨率约束View</h5><table>
<thead>
<tr>
<th>约束属性</th>
<th>描述</th>
<th>约束属性</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>android:minWidth</td>
<td></td>
<td>android:minHeight</td>
<td></td>
</tr>
<tr>
<td>android:maxWidth</td>
<td></td>
<td>android:maxHeight</td>
<td></td>
</tr>
</tbody></table>
<p>2.6.1 百分比</p>
<figure class="highlight xml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="tag">&lt;<span class="name">Button</span> <span class="attr">android:id</span>=<span class="string">&quot;@+id/buttonA&quot;</span> </span></span><br><span class="line"><span class="tag">    <span class="attr">android:layout_width</span>=<span class="string">&quot;0dp&quot;</span></span></span><br><span class="line"><span class="tag">    <span class="attr">app:layout_constraintWidth_default</span>=<span class="string">&quot;percent&quot;</span></span></span><br><span class="line"><span class="tag">    <span class="attr">app:layout_constraintWidth_percent</span>=<span class="string">&quot;0.5&quot;</span></span></span><br><span class="line"><span class="tag">/&gt;</span></span><br></pre></td></tr></table></figure>
<p>2.6.2 比率<br>宽高一比一：</p>
<figure class="highlight xml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="tag">&lt;<span class="name">Button</span> <span class="attr">android:id</span>=<span class="string">&quot;@+id/buttonA&quot;</span> </span></span><br><span class="line"><span class="tag">    <span class="attr">android:layout_height</span>=<span class="string">&quot;0dp&quot;</span></span></span><br><span class="line"><span class="tag">    <span class="attr">app:layout_constraintDimensionRatio</span>=<span class="string">&quot;1:1&quot;</span></span></span><br><span class="line"><span class="tag">/&gt;</span></span><br></pre></td></tr></table></figure>
<p>指定一条边符合约束比率：</p>
<figure class="highlight xml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="tag">&lt;<span class="name">Button</span> <span class="attr">android:layout_width</span>=<span class="string">&quot;0dp&quot;</span></span></span><br><span class="line"><span class="tag">        <span class="attr">android:layout_height</span>=<span class="string">&quot;0dp&quot;</span></span></span><br><span class="line"><span class="tag">        <span class="attr">app:layout_constraintDimensionRatio</span>=<span class="string">&quot;H,16:9&quot;</span></span></span><br><span class="line"><span class="tag">        <span class="attr">app:layout_constraintBottom_toBottomOf</span>=<span class="string">&quot;parent&quot;</span></span></span><br><span class="line"><span class="tag">        <span class="attr">app:layout_constraintTop_toTopOf</span>=<span class="string">&quot;parent&quot;</span>/&gt;</span></span><br></pre></td></tr></table></figure>

<h5 id="2-7-通过链⛓约束View"><a href="#2-7-通过链⛓约束View" class="headerlink" title="2.7 通过链⛓约束View"></a>2.7 通过链⛓约束View</h5><table>
    <tr>
        <td><img src="../images/constraint/constraint_chain.png" width="300"/></td>
        <td><img src="../images/constraint/constraint_chain_head.png" width="300"/></td>
    </tr>
</table>

<table>
    <tr>
        <td>图示</td>
        <td>Style</td>
    </tr>
    <tr>
        <td><img src="../images/constraint/constraint_chain_spread.png" width="250"/></td>
        <td>Spread Chain</td>
    </tr>
     <tr>
      <td><img src="../images/constraint/constraint_chain_spread_inside.png" width="250"/></td>
      <td>Spread Inside Chain</td>
     </tr>
     <tr>
     <td><img src="../images/constraint/constraint_chain_weight.png" width="250"/></td>
     <td>Weighted Chain</td>
     </tr>
     <tr>
     <td><img src="../images/constraint/constraint_chain_packed.png" width="250"/></td>
     <td>Packed Chain</td>
     </tr>
     <tr>
     <td><img src="../images/constraint/constraint_chain_bias.png" width="250"/></td>
     <td>Packed Chain with Bias</td>
     </tr>
</table>

<h5 id="2-8-Barrier"><a href="#2-8-Barrier" class="headerlink" title="2.8 Barrier"></a>2.8 Barrier</h5><p>将多个View的某一边的极端值作为约束：</p>
<table>
    <tr>
        <td><img src="../images/constraint/constraint_barrier_start.png" width="300"/></td>
        <td><img src="../images/constraint/constraint_barrier_end.png" width="300"/></td>
    </tr>
</table>
<figure class="highlight xml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="tag">&lt;<span class="name">androidx.constraintlayout.widget.Barrier</span></span></span><br><span class="line"><span class="tag">              <span class="attr">android:id</span>=<span class="string">&quot;@+id/barrier&quot;</span></span></span><br><span class="line"><span class="tag">              <span class="attr">android:layout_width</span>=<span class="string">&quot;wrap_content&quot;</span></span></span><br><span class="line"><span class="tag">              <span class="attr">android:layout_height</span>=<span class="string">&quot;wrap_content&quot;</span></span></span><br><span class="line"><span class="tag">              <span class="attr">app:barrierDirection</span>=<span class="string">&quot;start/end&quot;</span></span></span><br><span class="line"><span class="tag">              <span class="attr">app:constraint_referenced_ids</span>=<span class="string">&quot;button1,button2&quot;</span> /&gt;</span></span><br></pre></td></tr></table></figure>

<h5 id="2-9-Group分组约束"><a href="#2-9-Group分组约束" class="headerlink" title="2.9 Group分组约束"></a>2.9 Group分组约束</h5><p>将多个View作为一个组一起控制：</p>
<figure class="highlight xml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="tag">&lt;<span class="name">androidx.constraintlayout.widget.Group</span></span></span><br><span class="line"><span class="tag">              <span class="attr">android:id</span>=<span class="string">&quot;@+id/group&quot;</span></span></span><br><span class="line"><span class="tag">              <span class="attr">android:layout_width</span>=<span class="string">&quot;wrap_content&quot;</span></span></span><br><span class="line"><span class="tag">              <span class="attr">android:layout_height</span>=<span class="string">&quot;wrap_content&quot;</span></span></span><br><span class="line"><span class="tag">              <span class="attr">android:visibility</span>=<span class="string">&quot;visible&quot;</span></span></span><br><span class="line"><span class="tag">              <span class="attr">app:constraint_referenced_ids</span>=<span class="string">&quot;button4,button9&quot;</span> /&gt;</span></span><br></pre></td></tr></table></figure>

<h5 id="2-10-Placeholder占位约束"><a href="#2-10-Placeholder占位约束" class="headerlink" title="2.10 Placeholder占位约束"></a>2.10 Placeholder占位约束</h5><p>&ensp;&ensp;&ensp;&ensp;Placeholder是一个虚拟的占位符View，界面上其他存在的View可以通过<code>placeholder.setContentId(R.id.xxx)</code>将自己的位置设置到placeholder的位置，原位置视图将不可见。<br>&ensp;&ensp;&ensp;&ensp;我们可以使用Placeholder搭建一个布局模板，include到其他布局当中，来填充模板中的视图，这将使所有的界面有一个通用的模板。</p>
<h5 id="2-11-Guideline引导线约束"><a href="#2-11-Guideline引导线约束" class="headerlink" title="2.11 Guideline引导线约束"></a>2.11 Guideline引导线约束</h5><p>Guideline只能在ConstraintLayout中使用，在水平或垂直方向设置辅助布局的不可见线条。</p>
<table>
<thead>
<tr>
<th>约束属性</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>layout_constraintGuide_begin</td>
<td>距布局的左边或者上边x处设置引导线</td>
</tr>
<tr>
<td>layout_constraintGuide_end</td>
<td>距布局右边或下面x处设置引导线</td>
</tr>
<tr>
<td>layout_constraintGuide_percent</td>
<td>宽或高的百分之x处设置引导线</td>
</tr>
</tbody></table>
<figure class="highlight xml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="tag">&lt;<span class="name">androidx.constraintlayout.widget.ConstraintLayout</span></span></span><br><span class="line"><span class="tag">        <span class="attr">xmlns:android</span>=<span class="string">&quot;http://schemas.android.com/apk/res/android&quot;</span></span></span><br><span class="line"><span class="tag">        <span class="attr">xmlns:app</span>=<span class="string">&quot;http://schemas.android.com/apk/res-auto&quot;</span></span></span><br><span class="line"><span class="tag">        <span class="attr">xmlns:tools</span>=<span class="string">&quot;http://schemas.android.com/tools&quot;</span></span></span><br><span class="line"><span class="tag">        <span class="attr">android:layout_width</span>=<span class="string">&quot;match_parent&quot;</span></span></span><br><span class="line"><span class="tag">        <span class="attr">android:layout_height</span>=<span class="string">&quot;match_parent&quot;</span>&gt;</span></span><br><span class="line"></span><br><span class="line">    <span class="tag">&lt;<span class="name">androidx.constraintlayout.widget.Guideline</span></span></span><br><span class="line"><span class="tag">            <span class="attr">android:layout_width</span>=<span class="string">&quot;wrap_content&quot;</span></span></span><br><span class="line"><span class="tag">            <span class="attr">android:layout_height</span>=<span class="string">&quot;wrap_content&quot;</span></span></span><br><span class="line"><span class="tag">            <span class="attr">android:id</span>=<span class="string">&quot;@+id/guideline&quot;</span></span></span><br><span class="line"><span class="tag">            <span class="attr">app:layout_constraintGuide_begin</span>=<span class="string">&quot;100dp&quot;</span></span></span><br><span class="line"><span class="tag">            <span class="attr">android:orientation</span>=<span class="string">&quot;vertical&quot;</span>/&gt;</span></span><br><span class="line"></span><br><span class="line">    <span class="tag">&lt;<span class="name">Button</span></span></span><br><span class="line"><span class="tag">            <span class="attr">android:text</span>=<span class="string">&quot;Button&quot;</span></span></span><br><span class="line"><span class="tag">            <span class="attr">android:layout_width</span>=<span class="string">&quot;wrap_content&quot;</span></span></span><br><span class="line"><span class="tag">            <span class="attr">android:layout_height</span>=<span class="string">&quot;wrap_content&quot;</span></span></span><br><span class="line"><span class="tag">            <span class="attr">android:id</span>=<span class="string">&quot;@+id/button&quot;</span></span></span><br><span class="line"><span class="tag">            <span class="attr">app:layout_constraintLeft_toLeftOf</span>=<span class="string">&quot;@+id/guideline&quot;</span></span></span><br><span class="line"><span class="tag">            <span class="attr">android:layout_marginTop</span>=<span class="string">&quot;16dp&quot;</span></span></span><br><span class="line"><span class="tag">            <span class="attr">app:layout_constraintTop_toTopOf</span>=<span class="string">&quot;parent&quot;</span> /&gt;</span></span><br><span class="line"></span><br><span class="line"><span class="tag">&lt;/<span class="name">androidx.constraintlayout.widget.ConstraintLayout</span>&gt;</span></span><br></pre></td></tr></table></figure>

<h4 id="三、原理"><a href="#三、原理" class="headerlink" title="三、原理"></a>三、原理</h4><h5 id="3-1-解决约束问题"><a href="#3-1-解决约束问题" class="headerlink" title="3.1 解决约束问题"></a>3.1 解决约束问题</h5><p>3.1.1 定义变量</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">x[1], x[2], ... x[n]</span><br></pre></td></tr></table></figure>
<p>3.1.2 定义约束问题：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">a[1]x[1] + ... + a[n]x[n] = b</span><br><span class="line">a[1]x[1] + ... + a[n]x[n] &lt;= b</span><br><span class="line">a[1]x[1] + ... + a[n]x[n] &gt;= b</span><br></pre></td></tr></table></figure>
<p>3.2.3 计算约束方程<br>食火鸡算法：食火鸡是一种生活在新几内亚热带雨林中的鸟类，以水果为食。同时它也是一种解决线性方程和线性不等式的算法。1990年在华盛顿大学被证明和发现。线性方程非常适合用于表示用户界面中视图的位置、大小、与其他视图的关系。</p>
<h5 id="3-2-个人理解："><a href="#3-2-个人理解：" class="headerlink" title="3.2 个人理解："></a>3.2 个人理解：</h5><p>定义变量 -&gt; 声明View对象<br>定义约束问题 -&gt; 建立View之间的约束关系<br>计算约束方程 -&gt; 计算视图的大小、坐标  </p>
<h4 id="四、参考文档"><a href="#四、参考文档" class="headerlink" title="四、参考文档"></a>四、参考文档</h4><p><a target="_blank" rel="noopener" href="https://developer.android.com/reference/androidx/constraintlayout/widget/ConstraintLayout">1.官方文档</a><br><a target="_blank" rel="noopener" href="https://constraintlayout.com/layouts/">2.基本使用</a><br><a target="_blank" rel="noopener" href="https://biaomingzhong.github.io/2017/constraintlayout-basics-chains-2/">3.基本使用-译文</a><br><a target="_blank" rel="noopener" href="https://wiresareobsolete.com/2016/07/constraintlayout-part-1/">4.ConstraintLayout, Inside and Out: Part 1</a><br><a target="_blank" rel="noopener" href="https://wiresareobsolete.com/2016/07/constraintlayout-part-2/">5.ConstraintLayout, Inside and Out: Part 2</a><br><a target="_blank" rel="noopener" href="https://constraints.cs.washington.edu/cassowary/cassowary-tr.pdf">6.线性约束解决算法</a><br><a target="_blank" rel="noopener" href="https://cassowary.readthedocs.io/en/latest/topics/theory.html">7.解决约束</a></p>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://wangduwei.top/cpu-cache-overview.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpeg">
      <meta itemprop="name" content="wangduwei">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="嗅不到北的狗子">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/cpu-cache-overview.html" class="post-title-link" itemprop="url">CPU的缓存</a>
        </h2>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>
              

              <time title="创建时间：2021-10-13 15:28:59 / 修改时间：16:00:14" itemprop="dateCreated datePublished" datetime="2021-10-13T15:28:59+08:00">2021-10-13</time>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/cpu-cache-overview.html#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/cpu-cache-overview.html" itemprop="commentCount"></span>
    </a>
  </span>
  
  <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="far fa-file-word"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>971</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="far fa-clock"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>1 分钟</span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h4 id="一、性能"><a href="#一、性能" class="headerlink" title="一、性能"></a>一、性能</h4><p>1.1 在分层存储结构中，随着存储容量的增加，延迟也随之增加。<a target="_blank" rel="noopener" href="https://gist.github.com/jboner/2841832">参考</a></p>
<p>从数据可以看出，L1缓存和主存访问速度相差200倍。</p>
<center>
    <img src="../images/cpu_cache_speed.png" width="500"/>
</center>


<h4 id="二、缓存行"><a href="#二、缓存行" class="headerlink" title="二、缓存行"></a>二、缓存行</h4><p>CPU缓存的基本单位是缓存行，主存数据和缓存的映射存在下列关系：</p>
<h5 id="2-1-直接映射缓存"><a href="#2-1-直接映射缓存" class="headerlink" title="2.1 直接映射缓存"></a>2.1 直接映射缓存</h5><center>
    <img src="../images/cpu_cache_direct_map.jpeg" width="600"/>
</center>

<p>1、 index用于计算在哪一个缓存行<br>2、 offset用于计算在缓存行的哪个字节<br>3、 tag用于判断缓存是否命中（假设0x7f6601 和 0x8f6602两个地址，低位都一样，缓存行和字节偏移都命中了，tag不命中）</p>
<p>缺点：<br>图中，cache缓存8行数据，当访问第0行、第8行、第16行时，缓存无法命中，每次都要去主存加载，发生<strong>缓存颠簸</strong></p>
<h5 id="2-2-多路组相连"><a href="#2-2-多路组相连" class="headerlink" title="2.2 多路组相连"></a>2.2 多路组相连</h5><p>这是一个两路组相连的示意图：</p>
<center>
    <img src="../images/cpu_cache_n_way.png" width="500"/>
</center>

<p>1、index定位组<br>2、组内依次对tag进行对比（可以通过硬件并行比较增加性能）</p>
<h4 id="三、缓存一致性"><a href="#三、缓存一致性" class="headerlink" title="三、缓存一致性"></a>三、缓存一致性</h4><h5 id="3-1-问题描述："><a href="#3-1-问题描述：" class="headerlink" title="3.1 问题描述："></a>3.1 问题描述：</h5><center>
    <img src="../images/cpu_cache_problem.jpeg" width="500"/>
</center>

<p>处理器 1 读 X ：从内存读取24并缓存<br>处理器 2 读 X ：从内存读取24并缓存<br>处理器 1 写 X = 32 ：更新自己的缓存<br>处理器 3 读 X = ？  </p>
<p>如何保证缓存的一致性？<a target="_blank" rel="noopener" href="https://people.eecs.berkeley.edu/~pattrsn/252F96/Lecture18.pdf">参考</a></p>
<h5 id="3-2-解决方案"><a href="#3-2-解决方案" class="headerlink" title="3.2 解决方案"></a>3.2 解决方案</h5><p>3.1.1 嗅探-Snooping Solution(Snoopy Bus)</p>
<p>根据写操作对缓存数据的影响嗅探协议可分为：<br>Write-invalidate：<br>当处理器写入数据时，所有的独立缓存将通过总线嗅探得到通知，并标志自己的缓存失效。这保证了全局只有一份缓存是有效的。</p>
<ul>
<li>MSI</li>
<li>MESI</li>
<li>MOSI</li>
<li>MOESI</li>
<li>MESIF </li>
</ul>
<p>Write-update：<br>当处理器写入数据时，所有的独立缓存将通过总线嗅探得到通知，并更新自己的缓存。通过总线广播给所有的缓存造成了总线繁忙，所以不常见。</p>
<p>3.1.2 目录-Directory-Based Schemes</p>
<h5 id="3-2-MESI协议参考"><a href="#3-2-MESI协议参考" class="headerlink" title="3.2 MESI协议参考"></a>3.2 MESI协议<a target="_blank" rel="noopener" href="https://people.cs.pitt.edu/~melhem/courses/2410p/ch5-4.pdf">参考</a></h5><p>MESI是四个状态的首字母缩写，在缓存行中用2个bit标志该缓存行的状态。</p>
<ul>
<li>M:Modified（只存在当前缓存行，已被修改，和主存不一致，需要更新回主存）</li>
<li>E:Exclusive（只存在当前缓存行，和主存一致）</li>
<li>S:Shared（其他缓存行也存在该数据，和主存一致）</li>
<li>I:Invalid（此缓存行失效）</li>
</ul>
<p>MESI的状态迁移：</p>
<center>
    <img src="../images/cpu_cache_mesi_state.jpeg" width="500"/>
</center>




<h4 id="四、参考文献"><a href="#四、参考文献" class="headerlink" title="四、参考文献"></a>四、参考文献</h4><p><a target="_blank" rel="noopener" href="https://www.cnkirito.moe/cache-line/#%E4%BB%80%E4%B9%88%E6%98%AF%E7%BC%93%E5%AD%98%E8%A1%8C-Cache-Line-%EF%BC%9F">0.Java角度理解CPU缓存</a><br><a target="_blank" rel="noopener" href="https://zhuanlan.zhihu.com/p/102293437">1.Cache的基本原理</a><br><a target="_blank" rel="noopener" href="https://gist.github.com/jboner/2841832">2.每个开发者需要知道的数据</a><br><a target="_blank" rel="noopener" href="https://medium.com/fcamels-notes/%E5%BE%9E%E7%A1%AC%E9%AB%94%E8%A7%80%E9%BB%9E%E4%BA%86%E8%A7%A3-memry-barrier-%E7%9A%84%E5%AF%A6%E4%BD%9C%E5%92%8C%E6%95%88%E6%9E%9C-416ff0a64fc1">3.硬件角度看内存屏障</a><br><a target="_blank" rel="noopener" href="https://medium.com/fcamels-notes/%E5%BE%9E-double-checked-locking-%E4%BA%86%E8%A7%A3-memory-barrier-%E7%9A%84%E4%BD%9C%E7%94%A8-bb151a359c1b">4.软件角度内存屏障</a><br><a target="_blank" rel="noopener" href="https://stackoverflow.com/questions/3928995/how-do-cache-lines-work">5.stackoverflow-How do cache lines work?</a><br><a target="_blank" rel="noopener" href="https://courses.cs.duke.edu/spring09/cps104/lectures/2up-lecture17.pdf">6.courses-pdf</a></p>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://wangduwei.top/java-object-layout.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpeg">
      <meta itemprop="name" content="wangduwei">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="嗅不到北的狗子">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/java-object-layout.html" class="post-title-link" itemprop="url">对象的内存布局</a>
        </h2>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2021-10-03 15:59:09" itemprop="dateCreated datePublished" datetime="2021-10-03T15:59:09+08:00">2021-10-03</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2021-10-05 16:03:56" itemprop="dateModified" datetime="2021-10-05T16:03:56+08:00">2021-10-05</time>
              </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/JVM/" itemprop="url" rel="index"><span itemprop="name">JVM</span></a>
                </span>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/java-object-layout.html#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/java-object-layout.html" itemprop="commentCount"></span>
    </a>
  </span>
  
  <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="far fa-file-word"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>3.3k</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="far fa-clock"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>3 分钟</span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h4 id="一、概述"><a href="#一、概述" class="headerlink" title="一、概述"></a>一、概述</h4><p>很多时候我们都有一个疑问：一个对象在内存中占用多大的空间呢？</p>
<figure class="highlight shell"><figcaption><span>script</span></figcaption><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">$</span><span class="bash"> jdk8-64/java -jar jol-cli.jar internals java.lang.Object</span></span><br><span class="line"><span class="meta">#</span><span class="bash"> Running 64-bit HotSpot VM.</span></span><br><span class="line"><span class="meta">#</span><span class="bash"> Using compressed oop with 3-bit <span class="built_in">shift</span>.</span></span><br><span class="line"><span class="meta">#</span><span class="bash"> Using compressed klass with 3-bit <span class="built_in">shift</span>.</span></span><br><span class="line"></span><br><span class="line">Instantiated the sample instance via default constructor.</span><br><span class="line"></span><br><span class="line">java.lang.Object object internals:</span><br><span class="line"> OFFSET  SIZE   TYPE DESCRIPTION                  VALUE</span><br><span class="line">      0     4        (object header)              05 00 00 00 # Mark word</span><br><span class="line">      4     4        (object header)              00 00 00 00 # Mark word</span><br><span class="line">      8     4        (object header)              00 10 00 00 # (not mark word)</span><br><span class="line">     12     4        (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 4 bytes external = 4 bytes total</span><br></pre></td></tr></table></figure>

<p>通过OpenJDK的Java-Object-Layout我们看到<code>java.lang.Object</code>的一个实例占用16 bytes。</p>
<p>同样的<code>java.lang.Boolean</code>类型占用的字节数：</p>
<figure class="highlight shell"><figcaption><span>script</span></figcaption><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">java.lang.Boolean object internals:</span><br><span class="line"> OFFSET  SIZE      TYPE DESCRIPTION                               VALUE</span><br><span class="line">      0    12           (object header)                           N/A</span><br><span class="line">     12     1   boolean Boolean.value                             N/A</span><br><span class="line">     13     3           (loss due to the next object alignment)</span><br><span class="line">Instance size: 16 bytes</span><br><span class="line">Space losses: 0 bytes internal + 3 bytes external = 3 bytes total</span><br></pre></td></tr></table></figure>

<figure class="highlight shell"><figcaption><span>script</span></figcaption><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">[HEADER: 12 bytes]  12 </span><br><span class="line">[value:   1 byte ]  13</span><br><span class="line">[padding: 3 bytes]  16</span><br></pre></td></tr></table></figure>

<p>其实一个对象通常由三块组成，分别是：对象头、实例数据和对齐填充。</p>
<h4 id="二、对象头（object-header）"><a href="#二、对象头（object-header）" class="headerlink" title="二、对象头（object header）"></a>二、对象头（object header）</h4><p>在前面通过JOL打印输出的关于java.lang.Object信息中，我们看到object header占用12字节，但是输出并没有包含详细的结构信息，我们可以通过<a target="_blank" rel="noopener" href="http://hg.openjdk.java.net/jdk/jdk/file/19afeaa0fdbe/src/hotspot/share/oops/oop.hpp#l52">Hotspot的源码</a>了解到对象头包含两个部分：<strong>mark word</strong>和<strong>class word</strong>。</p>
<h5 id="2-1-mark-word："><a href="#2-1-mark-word：" class="headerlink" title="2.1 mark word："></a>2.1 <a target="_blank" rel="noopener" href="http://hg.openjdk.java.net/jdk/jdk/file/19afeaa0fdbe/src/hotspot/share/oops/markWord.hpp#l33">mark word</a>：</h5><p>mark word在32位和64位机分别占32位和64位，当其中锁标志位的值不同时，它前面的bit存储不同的含义。</p>
<ul>
<li>存储对象的gc年龄信息</li>
<li>存储Hashcode</li>
<li>存储锁信息</li>
</ul>
<center>
    <img src="../images/mark-word-64bit.png" width="600"/>
</center>

<h5 id="2-2-class-word"><a href="#2-2-class-word" class="headerlink" title="2.2 class word:"></a>2.2 class word:</h5><p>代码运行的时候，对象只是一串字节，我们可以通过class-word获取一些对象的元信息，它存储指向方法区中表示对象类型的指针，比如以下使用场景：</p>
<ul>
<li>运行时类型检查</li>
<li>决定对象大小</li>
<li>计算接口调用的目标类</li>
</ul>
<h5 id="2-3-数组长度："><a href="#2-3-数组长度：" class="headerlink" title="2.3 数组长度："></a>2.3 数组长度：</h5><p>如果是数组类型，对象头会额外存储数组的长度信息。</p>
<ul>
<li>快速计算对象的大小</li>
<li>数组边界检查</li>
</ul>
<h4 id="三、实例数据和对齐填充"><a href="#三、实例数据和对齐填充" class="headerlink" title="三、实例数据和对齐填充"></a>三、实例数据和对齐填充</h4><p>实例数据即我们在代码中声明的变量等信息，它的存储受到一些规则的约束以及虚拟机参数的控制。</p>
<h5 id="3-1-没有属性的类的内存布局"><a href="#3-1-没有属性的类的内存布局" class="headerlink" title="3.1 没有属性的类的内存布局"></a>3.1 没有属性的类的内存布局</h5><blockquote>
<p>规则一：每个对象都是八字节对齐。</p>
</blockquote>
<p>从前面Object的输出中，我们看到，当一个对象只有头部信息时占用16byte，刚好是8的整数倍。</p>
<h5 id="3-2-Object子类的内存布局"><a href="#3-2-Object子类的内存布局" class="headerlink" title="3.2 Object子类的内存布局"></a>3.2 Object子类的内存布局</h5><p>跟在对象头后面的类属性按照它们的大小在内存中排序，例如：int是4字节、long是8字节。采用字节对齐可以提高性能，因为从内存读取4字节到4字节的寄存器性能更好。</p>
<p>为了节约内存，Sun的虚拟机在分配对象字段的时候和它们声明的顺序不同，有如下顺序规则：</p>
<p>1、double和long类型<br>2、int和float<br>3、short和char<br>4、boolean和byte<br>5、reference</p>
<p>为什么可以优化内存呢？我们看一下这个例子：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">MyClass</span> </span>&#123;</span><br><span class="line">    <span class="keyword">byte</span> a;</span><br><span class="line">    <span class="keyword">int</span> c;</span><br><span class="line">    <span class="keyword">boolean</span> d;</span><br><span class="line">    <span class="keyword">long</span> e;</span><br><span class="line">    Object f;        </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>它的对象布局如下：</p>
<figure class="highlight shell"><figcaption><span>script</span></figcaption><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">[HEADER:  8 bytes]  8</span><br><span class="line">[a:       1 byte ]  9</span><br><span class="line">[padding: 3 bytes] 12</span><br><span class="line">[c:       4 bytes] 16</span><br><span class="line">[d:       1 byte ] 17</span><br><span class="line">[padding: 7 bytes] 24</span><br><span class="line">[e:       8 bytes] 32</span><br><span class="line">[f:       4 bytes] 36</span><br><span class="line">[padding: 4 bytes] 40</span><br></pre></td></tr></table></figure>
<p>总共使用了40字节内存，其中14个用于内存对齐而浪费掉。如果重排顺序则：</p>
<figure class="highlight shell"><figcaption><span>script</span></figcaption><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">[HEADER:  8 bytes]  8</span><br><span class="line">[e:       8 bytes] 16</span><br><span class="line">[c:       4 bytes] 20</span><br><span class="line">[a:       1 byte ] 21</span><br><span class="line">[d:       1 byte ] 22</span><br><span class="line">[padding: 2 bytes] 24</span><br><span class="line">[f:       4 bytes] 28</span><br><span class="line">[padding: 4 bytes] 32</span><br></pre></td></tr></table></figure>

<p>经过优化后只有6个字节用于对齐填充，总内存也只有32byte。</p>
<h5 id="3-3-子类的内存布局"><a href="#3-3-子类的内存布局" class="headerlink" title="3.3 子类的内存布局"></a>3.3 子类的内存布局</h5><blockquote>
<p>规则三：继承结构中属于不同类的字段不混合在一起。父类优先，子类其次。</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">A</span> </span>&#123;</span><br><span class="line">   <span class="keyword">long</span> a;</span><br><span class="line">   <span class="keyword">int</span> b;</span><br><span class="line">   <span class="keyword">int</span> c;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">B</span> <span class="keyword">extends</span> <span class="title">A</span> </span>&#123;</span><br><span class="line">   <span class="keyword">long</span> d;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>B类的布局如下：</p>
<figure class="highlight shell"><figcaption><span>script</span></figcaption><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">[HEADER:  8 bytes]  8</span><br><span class="line">[a:       8 bytes] 16</span><br><span class="line">[b:       4 bytes] 20</span><br><span class="line">[c:       4 bytes] 24</span><br><span class="line">[d:       8 bytes] 32</span><br></pre></td></tr></table></figure>

<p>如果父类的字段不符合4字节对齐。</p>
<blockquote>
<p>规则四：父类的最后一个字段和子类第一个字段之间必须4字节对齐。</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">A</span> </span>&#123;</span><br><span class="line">   <span class="keyword">byte</span> a;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">B</span> </span>&#123;</span><br><span class="line">   <span class="keyword">byte</span> b;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight shell"><figcaption><span>script</span></figcaption><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">[HEADER:  8 bytes]  8</span><br><span class="line">[a:       1 byte ]  9</span><br><span class="line">[padding: 3 bytes] 12</span><br><span class="line">[b:       1 byte ] 13</span><br><span class="line">[padding: 3 bytes] 16</span><br></pre></td></tr></table></figure>
<p>a后面的3个字节就是为了使其4字节对齐。这3个字节只能浪费不能给B使用。</p>
<p>最后一个规则可以用于节约一些内存空间：当子类的第一个属性是long或者double类型且父类没有以8字节边界结束。</p>
<blockquote>
<p>规则五：子类的第一个字段是doubel或long且父类没有以8字节边界结束，JVM打破2的规则，先存储int、short、byte、reference来填补空缺。</p>
</blockquote>
<p>例如：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">A</span> </span>&#123;</span><br><span class="line">  <span class="keyword">byte</span> a;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">B</span> </span>&#123;</span><br><span class="line">  <span class="keyword">long</span> b;</span><br><span class="line">  <span class="keyword">short</span> c;  </span><br><span class="line">  <span class="keyword">byte</span> d;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>内存布局如下：</p>
<figure class="highlight shell"><figcaption><span>script</span></figcaption><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">[HEADER:  8 bytes]  8</span><br><span class="line">[a:       1 byte ]  9</span><br><span class="line">[padding: 3 bytes] 12</span><br><span class="line">[c:       2 bytes] 14</span><br><span class="line">[d:       1 byte ] 15</span><br><span class="line">[padding: 1 byte ] 16</span><br><span class="line">[b:       8 bytes] 24</span><br></pre></td></tr></table></figure>

<p>在字节12的位置，A类结束了。JVM打破2的规则放入short和byte类型，节约了4字节中的3个字节，否则将浪费掉。</p>
<h5 id="3-4-数组的内存布局"><a href="#3-4-数组的内存布局" class="headerlink" title="3.4 数组的内存布局"></a>3.4 数组的内存布局</h5><p>数组类型有一个额外的头部字段保存数组的长度，接下来是数组的元素，数组作为普通对象也是8字节对齐的。</p>
<p>这是byte[3]的布局：</p>
<figure class="highlight shell"><figcaption><span>script</span></figcaption><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">[HEADER:  12 bytes] 12</span><br><span class="line">[[0]:      1 byte ] 13</span><br><span class="line">[[1]:      1 byte ] 14</span><br><span class="line">[[2]:      1 byte ] 15</span><br><span class="line">[padding:  1 byte ] 16</span><br></pre></td></tr></table></figure>

<p>这是long[3]的布局:</p>
<figure class="highlight shell"><figcaption><span>script</span></figcaption><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">[HEADER:  12 bytes] 12</span><br><span class="line">[padding:  4 bytes] 16</span><br><span class="line">[[0]:      8 bytes] 24</span><br><span class="line">[[1]:      8 bytes] 32</span><br><span class="line">[[2]:      8 bytes] 40</span><br></pre></td></tr></table></figure>

<h5 id="3-5-内部类的内存布局"><a href="#3-5-内部类的内存布局" class="headerlink" title="3.5 内部类的内存布局"></a>3.5 内部类的内存布局</h5><p>非静态内部类有一个额外的隐藏字段，持有外部类的引用。这个字段是一个常规的引用,它符合对象在内存布局的规则。内部类因此有4字节额外的开销。</p>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://wangduwei.top/java-multithreading-synchronized.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpeg">
      <meta itemprop="name" content="wangduwei">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="嗅不到北的狗子">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/java-multithreading-synchronized.html" class="post-title-link" itemprop="url">Java synchronized</a>
        </h2>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2021-09-26 22:29:34" itemprop="dateCreated datePublished" datetime="2021-09-26T22:29:34+08:00">2021-09-26</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2021-10-05 16:01:43" itemprop="dateModified" datetime="2021-10-05T16:01:43+08:00">2021-10-05</time>
              </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/Java/" itemprop="url" rel="index"><span itemprop="name">Java</span></a>
                </span>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/java-multithreading-synchronized.html#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/java-multithreading-synchronized.html" itemprop="commentCount"></span>
    </a>
  </span>
  
  <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="far fa-file-word"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>3.7k</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="far fa-clock"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>3 分钟</span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h4 id="一、概述"><a href="#一、概述" class="headerlink" title="一、概述"></a>一、概述</h4><p>synchronized作为Java内建的关键字和锁机制，理解和使用它是必要的也是有难度的。个人认为深入理解此关键字在于以下几个方面：</p>
<ul>
<li>基础层面：正确理解对象锁和类锁，并熟练使用</li>
<li>能力提升：<ul>
<li>了解对象的内存布局，观察锁如何影响对象的内存布局</li>
<li>了解锁优化，锁升级及其过程</li>
</ul>
</li>
<li>更上一层楼：OpenJDK源码走读</li>
</ul>
<p>本文只是记录和翻译了一些英文文档的内容，作为笔记以后翻阅。详细内容可看原文。</p>
<h4 id="二、对象锁和类锁"><a href="#二、对象锁和类锁" class="headerlink" title="二、对象锁和类锁"></a>二、对象锁和类锁</h4><p>1.1 对象锁：修饰代码块和实例方法</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">ObjectLock</span> </span>&#123;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">test1</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">synchronized</span> (<span class="keyword">this</span>) &#123;<span class="comment">//此代码块锁住当前对象</span></span><br><span class="line">                <span class="keyword">int</span> i = <span class="number">5</span>;</span><br><span class="line">                <span class="keyword">while</span> (i-- &gt; <span class="number">0</span>) &#123;</span><br><span class="line">                    System.out.println(Thread.currentThread().getName() + <span class="string">&quot; : &quot;</span> + i);</span><br><span class="line">                    <span class="keyword">try</span> &#123;</span><br><span class="line">                        Thread.sleep(<span class="number">500</span>);</span><br><span class="line">                    &#125; <span class="keyword">catch</span> (InterruptedException ie) &#123;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">synchronized</span> <span class="keyword">void</span> <span class="title">test2</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">int</span> i = <span class="number">5</span>;</span><br><span class="line">            <span class="keyword">while</span> (i-- &gt; <span class="number">0</span>) &#123;</span><br><span class="line">                System.out.println(Thread.currentThread().getName() + <span class="string">&quot; : &quot;</span> + i);</span><br><span class="line">                <span class="keyword">try</span> &#123;</span><br><span class="line">                    Thread.sleep(<span class="number">500</span>);</span><br><span class="line">                &#125; <span class="keyword">catch</span> (InterruptedException ie) &#123;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>1.2 类锁:修饰代码块和静态方法</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"> <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">ClazzLock</span> </span>&#123;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">test1</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">synchronized</span> (ClazzLock.class) &#123;<span class="comment">//此代码块锁住class类</span></span><br><span class="line">                <span class="keyword">int</span> i = <span class="number">5</span>;</span><br><span class="line">                <span class="keyword">while</span> (i-- &gt; <span class="number">0</span>) &#123;</span><br><span class="line">                    System.out.println(Thread.currentThread().getName() + <span class="string">&quot; : &quot;</span> + i);</span><br><span class="line">                    <span class="keyword">try</span> &#123;</span><br><span class="line">                        Thread.sleep(<span class="number">500</span>);</span><br><span class="line">                    &#125; <span class="keyword">catch</span> (InterruptedException ie) &#123;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/**</span></span><br><span class="line"><span class="comment">         * 静态方法属于类</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">synchronized</span> <span class="keyword">void</span> <span class="title">test2</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">int</span> i = <span class="number">5</span>;</span><br><span class="line">            <span class="keyword">while</span> (i-- &gt; <span class="number">0</span>) &#123;</span><br><span class="line">                System.out.println(Thread.currentThread().getName() + <span class="string">&quot; : &quot;</span> + i);</span><br><span class="line">                <span class="keyword">try</span> &#123;</span><br><span class="line">                    Thread.sleep(<span class="number">500</span>);</span><br><span class="line">                &#125; <span class="keyword">catch</span> (InterruptedException ie) &#123;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="三、锁优化"><a href="#三、锁优化" class="headerlink" title="三、锁优化"></a>三、锁优化</h4><p>依据一：数据显示，许多锁有局部性特征，也就是说很多锁的锁定和释放都发生在特定的线程上。<br>依据二：数据显示，大部分Java对象不存在竞争。</p>
<ul>
<li>适应性自旋-Adaptive Spinning</li>
<li>锁消除-Lock Elimination</li>
<li>锁粗化-Lock Coarsening</li>
<li>轻量级锁-Lightweight Locking</li>
<li>偏向锁-Biased Locking</li>
</ul>
<h5 id="3-1-偏向锁"><a href="#3-1-偏向锁" class="headerlink" title="3.1 偏向锁"></a>3.1 偏向锁</h5><p>当我们开发了一个多线程环境下的模块时，其他人可能把它用在单线程环境下，此时加锁逻辑就是多余的。即使使用轻量级锁，每次获取锁都执行CAS原子指令也是一种性能损耗。使用偏向锁，线程首次获取锁时记录偏向于它自己,当有其他线程获取锁时，偏向锁要撤销，使用其他锁机制，如轻量级锁。</p>
<p>lock-field中有一个bit用于记录是否偏向状态，初始状态下是处于偏向锁状态，但没有设置偏向的线程ID。当线程首次获取锁时，发现没有指定偏向的线程，则使用CAS设置偏向线程，来避免竞态条件。</p>
<h5 id="3-2-轻量级锁（Thin-Lock）"><a href="#3-2-轻量级锁（Thin-Lock）" class="headerlink" title="3.2 轻量级锁（Thin Lock）"></a>3.2 轻量级锁（Thin Lock）</h5><p>相对于每次对象锁定都获取monitor结构的重量级锁而言，轻量级锁只是使用CAS原子指令修改lock-field（锁信息字段），因此轻量级锁不支持wait和notify。当发生锁竞争时，轻量级锁膨胀，同时分配monitor结构，lock-field更新成monitor的指针。</p>
<p>Java的锁是可重入的，所以需要记录当前锁的重入次数和锁的持有者。</p>
<ul>
<li>记录方式一：<br>最直接的方式是把lock-field分成两部分，一个记录锁的持有者，一个记录锁重入次数。由于lock-field字段长度固定，所以重入次数被限制了。重入次数达到上限只能升级为重量级锁。</li>
</ul>
<ul>
<li>记录方式二：<br>当线程需要获取锁时，在获取锁的线程栈中保存lock-records记录。线程获取的所有锁记录都将保存在这个集合中，它的顺序和获取锁的顺序一致。</li>
</ul>
<p>轻量级锁的变种和提升包含 <em>tasuki-lock</em> 和 <em>meta-lock</em> 其算法思想是一致的，差异在于实现细节，</p>
<p>1、轻量级锁的加锁过程</p>
<p>在代码进入同步块的时，如果同步对象锁状态为无锁（锁标志位为“01”，偏向锁位为“0”）虚拟机首先将在当前线程的栈帧中建立一个名为锁记录（Lock Record）的空间，用于存储锁对象目前的Mark Word的拷贝（官方称之为 Displaced Mark Word）。然后，虚拟机将使用CAS操作尝试将对象的Mark Word更新为指向Lock Record的指针，并将Lock record里的owner指针指向object mark word。如果这个更新动作成功了，那么这个线程就拥有了该对象的锁，并且对象Mark Word的锁标志位设置为“00”，即表示此对象处于轻量级锁定状态。</p>
<p>如果这个更新操作失败了，虚拟机首先会检查对象的Mark Word是否指向当前线程的栈帧，如果是就说明当前线程已经拥有了这个对象的锁，那就可以直接进入同步块继续执行。<br>否则说明多个线程竞争锁，轻量级锁就要膨胀为重量级锁，锁标志的状态值变为“10”，Mark Word中存储的就是指向重量级锁（互斥量）的指针，后面等待锁的线程也要进入阻塞状态。<br>而当前线程便尝试使用自旋来获取锁，自旋就是为了不让线程阻塞，而采用循环去获取锁的过程。</p>
<center>
    <img src="../images/java-thin-lock-recorder.jpg" width="500"/>
</center>

<pre><code>                 图2.1 轻量级锁CAS操作前/后堆栈与对象的状态
</code></pre>
<p>2、轻量级锁的解锁过程：</p>
<p>（1）通过CAS操作尝试把线程中复制的Displaced Mark Word对象替换当前的Mark Word。</p>
<p>（2）如果替换成功，整个同步过程就完成了。</p>
<p>（3）如果替换失败，说明有其他线程尝试过获取该锁（此时锁已膨胀），那就要在释放锁的同时，唤醒被挂起的线程。</p>
<h5 id="3-3-锁消除"><a href="#3-3-锁消除" class="headerlink" title="3.3 锁消除"></a>3.3 锁消除</h5><p>锁消除即删除不必要的加锁操作。根据代码逃逸技术，如果判断到一段代码中，堆上的数据不会逃逸出当前线程，那么可以认为这段代码是线程安全的，不必要加锁。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Test</span> <span class="keyword">extends</span> <span class="title">Thread</span></span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        contactString(<span class="string">&quot;aa&quot;</span>, <span class="string">&quot;bb&quot;</span>, <span class="string">&quot;cc&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> String <span class="title">contactString</span><span class="params">(String s1, String s2, String s3)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> StringBuffer().append(s1).append(s2).append(s3).toString();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>虽然StringBuffer的append是一个同步方法，但是这段程序中的StringBuffer属于一个局部变量，并且不会从该方法中逃逸出去，所以其实这过程是线程安全的，可以将锁消除。</p>
<h5 id="3-4-锁粗化"><a href="#3-4-锁粗化" class="headerlink" title="3.4 锁粗化"></a>3.4 锁粗化</h5><p>虚拟机对连续的加锁操作（synchronized append）进行范围扩展（粗化）到整个操作序列的外部。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> String <span class="title">concatString</span><span class="params">(String s1,String s2, String s3)</span></span>&#123;</span><br><span class="line">    StringBuffer sb = <span class="keyword">new</span> StringBUffer();</span><br><span class="line">    sb.append(s1);</span><br><span class="line">    sb.append(s2);</span><br><span class="line">    sb.append(s3);</span><br><span class="line">    <span class="keyword">return</span> sb.toString();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="四、参考资料"><a href="#四、参考资料" class="headerlink" title="四、参考资料"></a>四、参考资料</h4><p>1.Evaluating and improving biased locking in the HotSpot virtual machine<br>2.<a target="_blank" rel="noopener" href="https://www.cnblogs.com/paddix/p/5405678.html">Java并发编程：Synchronized底层优化（偏向锁、轻量级锁）</a><br>3.<a target="_blank" rel="noopener" href="https://www.cnblogs.com/zhai1997/p/13546652.html">锁：锁优化（synchronized 锁升级过程、锁消除、锁粗化）</a><br>4.<a target="_blank" rel="noopener" href="https://wiki.openjdk.java.net/display/HotSpot/Synchronization">Synchronization</a></p>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://wangduwei.top/kotlin-lang-flow.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpeg">
      <meta itemprop="name" content="wangduwei">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="嗅不到北的狗子">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/kotlin-lang-flow.html" class="post-title-link" itemprop="url">Kotlin Flow 基础</a>
        </h2>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>
              

              <time title="创建时间：2021-09-25 15:27:31 / 修改时间：17:40:43" itemprop="dateCreated datePublished" datetime="2021-09-25T15:27:31+08:00">2021-09-25</time>
            </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/Kotlin/" itemprop="url" rel="index"><span itemprop="name">Kotlin</span></a>
                </span>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/kotlin-lang-flow.html#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/kotlin-lang-flow.html" itemprop="commentCount"></span>
    </a>
  </span>
  
  <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="far fa-file-word"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>5.1k</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="far fa-clock"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>5 分钟</span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h4 id="一、什么是Flow"><a href="#一、什么是Flow" class="headerlink" title="一、什么是Flow"></a>一、什么是Flow</h4><h5 id="1、如何通过同步和异步方式返回多个值？"><a href="#1、如何通过同步和异步方式返回多个值？" class="headerlink" title="1、如何通过同步和异步方式返回多个值？"></a>1、如何通过同步和异步方式返回多个值？</h5><p>1.1 同步方式返回多个值</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">simple</span><span class="params">()</span></span>: List&lt;<span class="built_in">Int</span>&gt; = listOf(<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>)</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">main</span><span class="params">()</span></span> &#123;</span><br><span class="line">    simple().forEach &#123; value -&gt; println(value) &#125; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>1.2 同步方式<strong>依次</strong>返回多个值</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">simple</span><span class="params">()</span></span>: Sequence&lt;<span class="built_in">Int</span>&gt; = sequence &#123; <span class="comment">// sequence builder</span></span><br><span class="line">    <span class="keyword">for</span> (i <span class="keyword">in</span> <span class="number">1.</span><span class="number">.3</span>) &#123;</span><br><span class="line">        Thread.sleep(<span class="number">1000</span>) <span class="comment">// pretend we are computing it</span></span><br><span class="line">        yield(i) <span class="comment">// yield next value</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">main</span><span class="params">()</span></span> &#123;</span><br><span class="line">    simple().forEach &#123; value -&gt; println(<span class="string">&quot;time = <span class="subst">$&#123;System.currentTimeMillis()&#125;</span> ,<span class="variable">$value</span>&quot;</span>) &#125; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>1.3 异步方式返回多个值</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">suspend</span> <span class="function"><span class="keyword">fun</span> <span class="title">simple</span><span class="params">()</span></span>: List&lt;<span class="built_in">Int</span>&gt; &#123;</span><br><span class="line">    delay(<span class="number">1000</span>) <span class="comment">// pretend we are doing something asynchronous here</span></span><br><span class="line">    <span class="keyword">return</span> listOf(<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>)</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">main</span><span class="params">()</span></span> = runBlocking&lt;<span class="built_in">Unit</span>&gt; &#123;</span><br><span class="line">    simple().forEach &#123; value -&gt; println(value) &#125; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>1.4 如何通过异步的方式<strong>依次</strong>返回多个值呢？</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">simple</span><span class="params">()</span></span>: Flow&lt;<span class="built_in">Int</span>&gt; = flow &#123; <span class="comment">// flow builder</span></span><br><span class="line">    <span class="keyword">for</span> (i <span class="keyword">in</span> <span class="number">1.</span><span class="number">.3</span>) &#123;</span><br><span class="line">        delay(<span class="number">100</span>) <span class="comment">// pretend we are doing something useful here</span></span><br><span class="line">        emit(i) <span class="comment">// emit next value</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">main</span><span class="params">()</span></span> = runBlocking&lt;<span class="built_in">Unit</span>&gt; &#123;</span><br><span class="line">    <span class="comment">// Launch a concurrent coroutine to check if the main thread is blocked</span></span><br><span class="line">    launch &#123;</span><br><span class="line">        <span class="keyword">for</span> (k <span class="keyword">in</span> <span class="number">1.</span><span class="number">.3</span>) &#123;</span><br><span class="line">            println(<span class="string">&quot;I&#x27;m not blocked <span class="variable">$k</span>&quot;</span>)</span><br><span class="line">            delay(<span class="number">100</span>)</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// Collect the flow</span></span><br><span class="line">    simple().collect &#123; value -&gt; println(value) &#125; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>通过flow，我们可以实现异步的数据流。</strong></p>
<h5 id="2、Flow是冷数据流"><a href="#2、Flow是冷数据流" class="headerlink" title="2、Flow是冷数据流"></a>2、Flow是冷数据流</h5><p>冷数据流：每次调用<code>collect</code>函数时都会触发执行</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">simple</span><span class="params">()</span></span>: Flow&lt;<span class="built_in">Int</span>&gt; = flow &#123; </span><br><span class="line">    println(<span class="string">&quot;Flow started&quot;</span>)</span><br><span class="line">    <span class="keyword">for</span> (i <span class="keyword">in</span> <span class="number">1.</span><span class="number">.3</span>) &#123;</span><br><span class="line">        delay(<span class="number">100</span>)</span><br><span class="line">        emit(i)</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">main</span><span class="params">()</span></span> = runBlocking&lt;<span class="built_in">Unit</span>&gt; &#123;</span><br><span class="line">    println(<span class="string">&quot;Calling simple function...&quot;</span>)</span><br><span class="line">    <span class="keyword">val</span> flow = simple()</span><br><span class="line">    println(<span class="string">&quot;Calling collect...&quot;</span>)</span><br><span class="line">    flow.collect &#123; value -&gt; println(value) &#125; </span><br><span class="line">    println(<span class="string">&quot;Calling collect again...&quot;</span>)</span><br><span class="line">    flow.collect &#123; value -&gt; println(value) &#125; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h5 id="3、Flow的取消"><a href="#3、Flow的取消" class="headerlink" title="3、Flow的取消"></a>3、Flow的取消</h5><figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">simple</span><span class="params">()</span></span>: Flow&lt;<span class="built_in">Int</span>&gt; = flow &#123; </span><br><span class="line">    <span class="keyword">for</span> (i <span class="keyword">in</span> <span class="number">1.</span><span class="number">.3</span>) &#123;</span><br><span class="line">        delay(<span class="number">100</span>)          </span><br><span class="line">        println(<span class="string">&quot;Emitting <span class="variable">$i</span>&quot;</span>)</span><br><span class="line">        emit(i)</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">main</span><span class="params">()</span></span> = runBlocking&lt;<span class="built_in">Unit</span>&gt; &#123;</span><br><span class="line">    withTimeoutOrNull(<span class="number">250</span>) &#123; <span class="comment">// Timeout after 250ms </span></span><br><span class="line">        simple().collect &#123; value -&gt; println(value) &#125; </span><br><span class="line">    &#125;</span><br><span class="line">    println(<span class="string">&quot;Done&quot;</span>)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<h5 id="4、如何构建Flow？"><a href="#4、如何构建Flow？" class="headerlink" title="4、如何构建Flow？"></a>4、如何构建Flow？</h5><ul>
<li><code>flow&#123; ... &#125;</code></li>
<li><code>flowOf</code></li>
<li><code>.asFlow()</code></li>
</ul>
<h5 id="5、Flow操作符"><a href="#5、Flow操作符" class="headerlink" title="5、Flow操作符"></a>5、Flow操作符</h5><p>5.1 中间操作符</p>
<ul>
<li>map</li>
<li>filter</li>
<li>transform</li>
<li>take</li>
</ul>
<p>5.2 终止操作符</p>
<ul>
<li>collect</li>
<li>toList / toSet</li>
<li>first / single</li>
<li>reduce / fold</li>
</ul>
<p>5.3 <code>buffer</code>当流的处理速度慢于发射速度时，通过buffer提前缓存可以提高效率： </p>
<p>优化前：耗时1200ms</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">simple</span><span class="params">()</span></span>: Flow&lt;<span class="built_in">Int</span>&gt; = flow &#123;</span><br><span class="line">    <span class="keyword">for</span> (i <span class="keyword">in</span> <span class="number">1.</span><span class="number">.3</span>) &#123;</span><br><span class="line">        delay(<span class="number">100</span>) <span class="comment">// pretend we are asynchronously waiting 100 ms</span></span><br><span class="line">        emit(i) <span class="comment">// emit next value</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">main</span><span class="params">()</span></span> = runBlocking&lt;<span class="built_in">Unit</span>&gt; &#123; </span><br><span class="line">    <span class="keyword">val</span> time = measureTimeMillis &#123;</span><br><span class="line">        simple().collect &#123; value -&gt; </span><br><span class="line">            delay(<span class="number">300</span>) <span class="comment">// pretend we are processing it for 300 ms</span></span><br><span class="line">            println(value) </span><br><span class="line">        &#125; </span><br><span class="line">    &#125;   </span><br><span class="line">    println(<span class="string">&quot;Collected in <span class="variable">$time</span> ms&quot;</span>)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>优化后：耗时1000ms</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">val</span> time = measureTimeMillis &#123;</span><br><span class="line">    simple()</span><br><span class="line">        .buffer() <span class="comment">// buffer emissions, don&#x27;t wait</span></span><br><span class="line">        .collect &#123; value -&gt; </span><br><span class="line">            delay(<span class="number">300</span>) <span class="comment">// pretend we are processing it for 300 ms</span></span><br><span class="line">            println(value) </span><br><span class="line">        &#125; </span><br><span class="line">&#125;   </span><br><span class="line">println(<span class="string">&quot;Collected in <span class="variable">$time</span> ms&quot;</span>)</span><br></pre></td></tr></table></figure>

<p>5.4 <code>conflate</code>当生产速度大于消费速度，忽略未来得及处理的值</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">val</span> time = measureTimeMillis &#123;</span><br><span class="line">    simple()</span><br><span class="line">        .conflate() <span class="comment">// conflate emissions, don&#x27;t process each one</span></span><br><span class="line">        .collect &#123; value -&gt; </span><br><span class="line">            delay(<span class="number">300</span>) <span class="comment">// pretend we are processing it for 300 ms</span></span><br><span class="line">            println(value) </span><br><span class="line">        &#125; </span><br><span class="line">&#125;   </span><br><span class="line">println(<span class="string">&quot;Collected in <span class="variable">$time</span> ms&quot;</span>)</span><br><span class="line"><span class="comment">//输出：</span></span><br><span class="line"><span class="comment">//1</span></span><br><span class="line"><span class="comment">//3</span></span><br><span class="line"><span class="comment">//Collected in 758 ms</span></span><br></pre></td></tr></table></figure>

<p>5.5 <code>collectLatest</code> 如果消费者很慢，取消它，新值过来时再重新启动。</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">val</span> time = measureTimeMillis &#123;</span><br><span class="line">    simple()</span><br><span class="line">        .collectLatest &#123; value -&gt; <span class="comment">// cancel &amp; restart on the latest value</span></span><br><span class="line">            println(<span class="string">&quot;Collecting <span class="variable">$value</span>&quot;</span>) </span><br><span class="line">            delay(<span class="number">300</span>) <span class="comment">// pretend we are processing it for 300 ms</span></span><br><span class="line">            println(<span class="string">&quot;Done <span class="variable">$value</span>&quot;</span>) </span><br><span class="line">        &#125; </span><br><span class="line">&#125;   </span><br><span class="line">println(<span class="string">&quot;Collected in <span class="variable">$time</span> ms&quot;</span>)</span><br><span class="line"><span class="comment">//output:</span></span><br><span class="line"><span class="comment">//Collecting 1</span></span><br><span class="line"><span class="comment">//Collecting 2</span></span><br><span class="line"><span class="comment">//Collecting 3</span></span><br><span class="line"><span class="comment">//Done 3</span></span><br><span class="line"><span class="comment">//Collected in 741 ms</span></span><br></pre></td></tr></table></figure>

<p>5.6 多个flow合并：zip / combine  </p>
<p>使用<code>zip</code>操作符</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">val</span> nums = (<span class="number">1.</span><span class="number">.3</span>).asFlow() <span class="comment">// numbers 1..3</span></span><br><span class="line"><span class="keyword">val</span> strs = flowOf(<span class="string">&quot;one&quot;</span>, <span class="string">&quot;two&quot;</span>, <span class="string">&quot;three&quot;</span>) <span class="comment">// strings </span></span><br><span class="line">nums.zip(strs) &#123; a, b -&gt; <span class="string">&quot;<span class="variable">$a</span> -&gt; <span class="variable">$b</span>&quot;</span> &#125; <span class="comment">// compose a single string</span></span><br><span class="line">    .collect &#123; println(it) &#125; <span class="comment">// collect and print</span></span><br><span class="line"><span class="comment">//output:</span></span><br><span class="line"><span class="comment">//1 -&gt; one</span></span><br><span class="line"><span class="comment">//2 -&gt; two</span></span><br><span class="line"><span class="comment">//3 -&gt; three</span></span><br></pre></td></tr></table></figure>

<p>当两个flow不同步时：</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//速度不同步时，使用zip，到达同步点才输出</span></span><br><span class="line"><span class="keyword">val</span> nums = (<span class="number">1.</span><span class="number">.3</span>).asFlow().onEach &#123; delay(<span class="number">300</span>) &#125; <span class="comment">// numbers 1..3 every 300 ms</span></span><br><span class="line"><span class="keyword">val</span> strs = flowOf(<span class="string">&quot;one&quot;</span>, <span class="string">&quot;two&quot;</span>, <span class="string">&quot;three&quot;</span>).onEach &#123; delay(<span class="number">400</span>) &#125; <span class="comment">// strings every 400 ms</span></span><br><span class="line"><span class="keyword">val</span> startTime = System.currentTimeMillis() <span class="comment">// remember the start time </span></span><br><span class="line">nums.zip(strs) &#123; a, b -&gt; <span class="string">&quot;<span class="variable">$a</span> -&gt; <span class="variable">$b</span>&quot;</span> &#125; <span class="comment">// compose a single string with &quot;zip&quot;</span></span><br><span class="line">    .collect &#123; value -&gt; <span class="comment">// collect and print </span></span><br><span class="line">        println(<span class="string">&quot;<span class="variable">$value</span> at <span class="subst">$&#123;System.currentTimeMillis() - startTime&#125;</span> ms from start&quot;</span>) </span><br><span class="line">    &#125; </span><br><span class="line"><span class="comment">//output:</span></span><br><span class="line"><span class="comment">//1 -&gt; one at 428 ms from start</span></span><br><span class="line"><span class="comment">//2 -&gt; two at 828 ms from start</span></span><br><span class="line"><span class="comment">//3 -&gt; three at 1230 ms from start</span></span><br></pre></td></tr></table></figure>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">////速度不同步时，使用combine，有值到达即输出，无视同步</span></span><br><span class="line"><span class="keyword">val</span> nums = (<span class="number">1.</span><span class="number">.3</span>).asFlow().onEach &#123; delay(<span class="number">300</span>) &#125; <span class="comment">// numbers 1..3 every 300 ms</span></span><br><span class="line"><span class="keyword">val</span> strs = flowOf(<span class="string">&quot;one&quot;</span>, <span class="string">&quot;two&quot;</span>, <span class="string">&quot;three&quot;</span>).onEach &#123; delay(<span class="number">400</span>) &#125; <span class="comment">// strings every 400 ms          </span></span><br><span class="line"><span class="keyword">val</span> startTime = System.currentTimeMillis() <span class="comment">// remember the start time </span></span><br><span class="line">nums.combine(strs) &#123; a, b -&gt; <span class="string">&quot;<span class="variable">$a</span> -&gt; <span class="variable">$b</span>&quot;</span> &#125; <span class="comment">// compose a single string with &quot;combine&quot;</span></span><br><span class="line">    .collect &#123; value -&gt; <span class="comment">// collect and print </span></span><br><span class="line">        println(<span class="string">&quot;<span class="variable">$value</span> at <span class="subst">$&#123;System.currentTimeMillis() - startTime&#125;</span> ms from start&quot;</span>) </span><br><span class="line">    &#125; </span><br><span class="line"><span class="comment">//output:</span></span><br><span class="line"><span class="comment">//1 -&gt; one at 452 ms from start</span></span><br><span class="line"><span class="comment">//2 -&gt; one at 651 ms from start</span></span><br><span class="line"><span class="comment">//2 -&gt; two at 854 ms from start</span></span><br><span class="line"><span class="comment">//3 -&gt; two at 952 ms from start</span></span><br><span class="line"><span class="comment">//3 -&gt; three at 1256 ms from start</span></span><br></pre></td></tr></table></figure>


<p>参考文档：<br><a target="_blank" rel="noopener" href="https://kotlinlang.org/docs/flow.html"> 1.官方文档</a></p>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://wangduwei.top/basic-encryption-algorithm.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpeg">
      <meta itemprop="name" content="wangduwei">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="嗅不到北的狗子">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/basic-encryption-algorithm.html" class="post-title-link" itemprop="url">对称/非对称加密和数字签名</a>
        </h2>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>
              

              <time title="创建时间：2021-09-14 21:31:08 / 修改时间：21:42:28" itemprop="dateCreated datePublished" datetime="2021-09-14T21:31:08+08:00">2021-09-14</time>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/basic-encryption-algorithm.html#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/basic-encryption-algorithm.html" itemprop="commentCount"></span>
    </a>
  </span>
  
  <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="far fa-file-word"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>1.2k</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="far fa-clock"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>1 分钟</span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h4 id="1-对称加解密的过程："><a href="#1-对称加解密的过程：" class="headerlink" title="1.对称加解密的过程："></a>1.对称加解密的过程：</h4><p>（大家用相同的钥匙来进行加解密）<br><del>发送端和接收端首先要共享相同的密钥k(即通信前双方都需要知道对应的密钥)才能进行通信。发送端用共享密钥k对明文p进行加密，得到密文c，并将得到的密文发送给接收端，接收端收到密文后，并用其相同的共享密钥k对密文进行解密，得出明文p。</del></p>
<p>一般加密和解密的算法是公开的，需要保持隐秘的是密钥k<br>流行的对称加密算法有：DES，Triple-DES，RC2和RC4，AES</p>
<h5 id="缺点："><a href="#缺点：" class="headerlink" title="缺点："></a>缺点：</h5><ul>
<li>发送方和接收方首先需要共享相同的密钥，即存在密钥k的分发问题，如何安全的把共享密钥在双方进行分享，这本身也是一个如何安全通信的问题，一种方法是提前双方约定好，不通过具体的通信进行协商，避免被监听和截获。另外一种方式，将是下面我们介绍的通过非对称加密信道进行对称密码的分发和共享，即混合加密系统。</li>
<li>密钥管理的复杂度问题。由于对称加密的密钥是一对一的使用方式，若一方要跟n方通信，则需要维护n对密钥。</li>
</ul>
<h5 id="优点："><a href="#优点：" class="headerlink" title="优点："></a>优点：</h5><ul>
<li>加密和解密的速度要比非对称加密快很多，因此常用非对称加密建立的安全信道进行共享密钥的分享，完成后，具体的加解密则使用对称加密。即混合加密系统。</li>
</ul>
<p>另外一个点需要重点说明的是，密钥k的长度对解密破解的难度有很重大的影响，k的长度越长，对应的密码空间就越大，遭到暴力破解或者词典破解的难度就更大，就更加安全。</p>
<center>
    <img src="../images/dcjm.png" width="400"/>
</center>

<h4 id="2-数字签名的过程："><a href="#2-数字签名的过程：" class="headerlink" title="2.数字签名的过程："></a>2.数字签名的过程：</h4><ul>
<li>发送方A首先对变长的报文提取成一个定长的摘要，一般是md5等</li>
<li>A对摘要应用了一个签名函数，并且用A自己的私钥作为参数，因为只有A才知道私钥，所以正确的签名会说明签名者就是其所有者。</li>
<li>一旦计算出签名，节点A就将其附加到报文的末尾，并将报文和签名一起都发送给B</li>
<li>在接收端B，首先会按照同样的算法计算出报文的摘要，然后对签名用A的公钥进行解码，得出解码后的摘要，两个摘要进行比较，则可以判断是否是A发送的且内容没被篡改过。</li>
</ul>
<center>
    <img src="../images/szqm.png" width="400"/>
</center>


<h4 id="3-非对称加解密的过程："><a href="#3-非对称加解密的过程：" class="headerlink" title="3.非对称加解密的过程："></a>3.非对称加解密的过程：</h4><p>加密一方找到接收方的公钥e (如何找到呢？大部分的公钥查找工作实际上都是通过数字证书来实现的)，然后用公钥e对明文p进行加密后得到密文c，并将得到的密文发送给接收方，接收方收到密文后，用自己保留的私钥d进行解密，得到明文p，需要注意的是：用公钥加密的密文，只有拥有私钥的一方才能解密，这样就可以解决加密的各方可以统一使用一个公钥即可。</p>
<p>常用的非对称加密算法有：RSA</p>
<h5 id="优点：-1"><a href="#优点：-1" class="headerlink" title="优点："></a>优点：</h5><ul>
<li>不存在密钥分发的问题，解码方可以自己生成密钥对，一个做私钥存起来，另外一个作为公钥进行发布。</li>
<li>解决了密钥管理的复杂度问题，多个加密方都可以使用一个已知的公钥进行加密，但只有拥有私钥的一方才能解密。</li>
</ul>
<h5 id="缺点：-1"><a href="#缺点：-1" class="headerlink" title="缺点："></a>缺点：</h5><ul>
<li>非对称加密不足的地方是加解密的速度没有对称加密快。</li>
</ul>
<p>综上，分析了对称加密和非对称加密各自的优缺点后，有没有一种办法是可以利用两者的优点但避开对应的缺点呢？答应是有的，实际上用得最多的是混合加密系统，比如在两个节点间通过便捷的公开密码加密技术建立起安全通信，然后再用安全的通信产生并发送临时的随机对称密钥，通过更快的对称加密技术对剩余的数据进行加密。</p>
<center>
    <img src="../images/fdcjm.png" width="400"/>
</center>
      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://wangduwei.top/principles-of-economics.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpeg">
      <meta itemprop="name" content="wangduwei">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="嗅不到北的狗子">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/principles-of-economics.html" class="post-title-link" itemprop="url">经济学的十大原理</a>
        </h2>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>
              

              <time title="创建时间：2021-09-09 22:58:09 / 修改时间：23:04:53" itemprop="dateCreated datePublished" datetime="2021-09-09T22:58:09+08:00">2021-09-09</time>
            </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/Economics/" itemprop="url" rel="index"><span itemprop="name">Economics</span></a>
                </span>
            </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/principles-of-economics.html#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/principles-of-economics.html" itemprop="commentCount"></span>
    </a>
  </span>
  
  <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="far fa-file-word"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>852</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="far fa-clock"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>1 分钟</span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h4 id="一、人们如何做出决策"><a href="#一、人们如何做出决策" class="headerlink" title="一、人们如何做出决策"></a>一、人们如何做出决策</h4><h5 id="1-1-人们面临权衡取舍"><a href="#1-1-人们面临权衡取舍" class="headerlink" title="1.1 人们面临权衡取舍"></a>1.1 人们面临权衡取舍</h5><p>选择一样东西就意味着你要放弃另外一样东西。认识到生活中的权衡是重要的，因为人们只有了解他们可以得到的选择，才能作出良好的决策。</p>
<h5 id="1-2-某种东西的成本是为了得到它而放弃的东西"><a href="#1-2-某种东西的成本是为了得到它而放弃的东西" class="headerlink" title="1.2 某种东西的成本是为了得到它而放弃的东西"></a>1.2 某种东西的成本是为了得到它而放弃的东西</h5><p>一种东西的机会成本是为了得到这种东西所放弃的东西</p>
<h5 id="1-3-理性人考虑边际量"><a href="#1-3-理性人考虑边际量" class="headerlink" title="1.3 理性人考虑边际量"></a>1.3 理性人考虑边际量</h5><p>生活中的许多决策涉及到对现有行动计划进行微小的增量调整。 经济学家把这些调整称为边际变动。<br>个人和企业通过考虑边际量将会作出更好的决策。只有一种行动的边际收益大于边际成本，一个理性决策者才 会采取这项行动。</p>
<h5 id="1-4-人们会对激励作出反应"><a href="#1-4-人们会对激励作出反应" class="headerlink" title="1.4 人们会对激励作出反应"></a>1.4 人们会对激励作出反应</h5><ul>
<li>由于理性人通过比较成本与收益🉐做出决策，所以他们会对激励做出反应。</li>
<li>在分析任何一种政策时，不仅应该考虑直接影响，而且还应该考 虑激励发生作用的间接影响。</li>
<li>如果政策改变了激励，它就将使人们改 变自己的行为。</li>
</ul>
<h4 id="二、人们如何相互影响"><a href="#二、人们如何相互影响" class="headerlink" title="二、人们如何相互影响"></a>二、人们如何相互影响</h4><h5 id="2-1-贸易能使每个人的状况变得更好"><a href="#2-1-贸易能使每个人的状况变得更好" class="headerlink" title="2.1 贸易能使每个人的状况变得更好"></a>2.1 贸易能使每个人的状况变得更好</h5><p>贸易使各国可以专 门从事自己最擅长活动，并享有很多的各种各样物品与劳务</p>
<h5 id="2-2-市场通常是组织经济活动的一种好方法"><a href="#2-2-市场通常是组织经济活动的一种好方法" class="headerlink" title="2.2 市场通常是组织经济活动的一种好方法"></a>2.2 市场通常是组织经济活动的一种好方法</h5><ul>
<li>在市场经济中，中央计划者的决策被千百万企业和家庭的决策所取代。</li>
<li>价格和利己引导人们决策</li>
<li>价格就是看不见的手用来指引经济活动的工具</li>
<li>当政府阻止价格根据供求状况自发调整时，他就限制了看不见的手🤚对组成经济的千百万家庭👪和企业的决策进行协调的能力</li>
</ul>
<h5 id="2-3-政府有时可以改善市场结果"><a href="#2-3-政府有时可以改善市场结果" class="headerlink" title="2.3 政府有时可以改善市场结果"></a>2.3 政府有时可以改善市场结果</h5><ul>
<li>只有在政府实施规则并维护对市场经济至关重要的制度时，看不见的手才能施展其魔力。</li>
<li>看不见的手🤚是强有力的，但并不是无所不能的。政府干预经济的原因有两类：促进效率和促进平等。</li>
</ul>
<h4 id="三、整体经济如何运行"><a href="#三、整体经济如何运行" class="headerlink" title="三、整体经济如何运行"></a>三、整体经济如何运行</h4><h5 id="3-1-一国的生活水平取决于它生产物品与服务的能力"><a href="#3-1-一国的生活水平取决于它生产物品与服务的能力" class="headerlink" title="3.1 一国的生活水平取决于它生产物品与服务的能力"></a>3.1 一国的生活水平取决于它生产物品与服务的能力</h5><p>生产率：每单位劳动投入所生产的物品与服务数量。</p>
<h5 id="3-2-当政府发行了过多货币时，物价上升"><a href="#3-2-当政府发行了过多货币时，物价上升" class="headerlink" title="3.2 当政府发行了过多货币时，物价上升"></a>3.2 当政府发行了过多货币时，物价上升</h5><h5 id="3-3-社会面临通货膨胀与失业之间的短期权衡取舍"><a href="#3-3-社会面临通货膨胀与失业之间的短期权衡取舍" class="headerlink" title="3.3 社会面临通货膨胀与失业之间的短期权衡取舍"></a>3.3 社会面临通货膨胀与失业之间的短期权衡取舍</h5><ul>
<li>货币的增加刺激社会的整体支出水平，从而增加对物品与服务的需求</li>
<li>需求的增加随着时间的推移，会引起企业提高物价，同时它也鼓励企业雇佣更多的工人👷，并生产更多的物品与服务</li>
<li>雇佣更多的工人👷意味着更少的失业。</li>
</ul>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  

      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://wangduwei.top/file-format-elf-relocation.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpeg">
      <meta itemprop="name" content="wangduwei">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="嗅不到北的狗子">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          
            <a href="/file-format-elf-relocation.html" class="post-title-link" itemprop="url">重定位</a>
        </h2>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2021-09-04 21:53:33" itemprop="dateCreated datePublished" datetime="2021-09-04T21:53:33+08:00">2021-09-04</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2021-09-07 23:12:26" itemprop="dateModified" datetime="2021-09-07T23:12:26+08:00">2021-09-07</time>
              </span>

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/file-format-elf-relocation.html#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/file-format-elf-relocation.html" itemprop="commentCount"></span>
    </a>
  </span>
  
  <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="far fa-file-word"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>1.2k</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="far fa-clock"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>1 分钟</span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
          <h4 id="一、可重定位文件"><a href="#一、可重定位文件" class="headerlink" title="一、可重定位文件"></a>一、可重定位文件</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">//main.c                    //x.c</span><br><span class="line"></span><br><span class="line">extern void foo(void);      |   #include &lt;stdio.h&gt;</span><br><span class="line">                            |</span><br><span class="line">int main(void)              |   void foo()</span><br><span class="line">&#123;                           |   &#123;</span><br><span class="line">    foo();                  |       printf(&quot;foo\n&quot;);</span><br><span class="line">    return 0;               |   &#125;</span><br><span class="line">&#125;                           |</span><br></pre></td></tr></table></figure>

<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">&gt; objdump -d main.o</span><br><span class="line">00000000 &lt;main&gt;:</span><br><span class="line">   0:	55                   	push   %ebp</span><br><span class="line">   1:	89 e5                	mov    %esp,%ebp</span><br><span class="line">   3:	83 e4 f0             	and    $0xfffffff0,%esp</span><br><span class="line">   6:	e8 fc ff ff ff       	call   7 &lt;main+0x7&gt;</span><br><span class="line">   b:	b8 00 00 00 00       	mov    $0x0,%eax</span><br><span class="line">  10:	c9                   	leave</span><br><span class="line">  11:	c3                   	ret</span><br></pre></td></tr></table></figure>

<p>在编译和汇编阶段，[main.c -&gt; main.o] 汇编器无法确定外部定义的函数和全局变量的地址，所以它只能使用一个假地址占位，并产生一条额外的记录，让后面的链接器使用这条记录帮它完成地址修正。这条记录对于代码段来说放在[.rel.text] ，对于数据段来说放在[.rel.data],它们都是重定位文件的一个section。</p>
<p>对于每一条记录都对应于如下的一个数据结构：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">typedef struct &#123;</span><br><span class="line">        Elf32_Addr r_offset;</span><br><span class="line">        uint32_t   r_info;</span><br><span class="line">        int32_t    r_addend;</span><br><span class="line">&#125; Elf32_Rela;</span><br></pre></td></tr></table></figure>


<h4 id="二、静态链接"><a href="#二、静态链接" class="headerlink" title="二、静态链接"></a>二、静态链接</h4><p>1、多个目标文件的合并:</p>
<center>
    <img src="../images/elf_obj_file_merge.png" width="500"/>
</center>

<p>2、对代码段，数据段以及各符号进行地址分配<br>3、根据 [relocation entries] 重新计算代码和数据段中的假地址。</p>
<h4 id="三、动态链接"><a href="#三、动态链接" class="headerlink" title="三、动态链接"></a>三、动态链接</h4><h5 id="1、静态链接的缺点"><a href="#1、静态链接的缺点" class="headerlink" title="1、静态链接的缺点"></a>1、静态链接的缺点</h5><ul>
<li>静态链接将使一些公用代码如libc库产生冗余，浪费内存和磁盘空间</li>
<li>如果模块化开发，一个模块更新就得重新链接</li>
</ul>
<h5 id="2、动态链接的概念"><a href="#2、动态链接的概念" class="headerlink" title="2、动态链接的概念"></a>2、动态链接的概念</h5><p>相较于静态链接在编译期进行链接操作，将链接过程推迟到运行时进行的过程叫动态链接。</p>
<h5 id="3、动态链接的实现"><a href="#3、动态链接的实现" class="headerlink" title="3、动态链接的实现"></a>3、动态链接的实现</h5><p>   3.1 地址无关代码<br>    由于在运行时，代码段是共享的，只能读不能写，所以需要将指令中那些需要修改的部分分离出来，跟数据部分放在一起，这样指令部分就可以保持不变，而数据部分可以在每一个进程中拥有一个副本。</p>
<p>   3.2 全局偏移表（Global Offset Table）<br>    当链接过程发生在运行期时，外部的符号调用只有在运行时装载模块后才能确定模块被装载的地址，以及模块内符号的确切地址。所以ELF提供了一个全局偏移表（GOT）来记录这些外部模块的符号引用。当模块被装载时，会更新此表的内容。</p>
<h4 id="四、参考文献"><a href="#四、参考文献" class="headerlink" title="四、参考文献"></a>四、参考文献</h4><p>1.<a target="_blank" rel="noopener" href="https://people.cs.pitt.edu/~xianeizhang/notes/Linking.html#symbol">Linking</a><br>2.<a target="_blank" rel="noopener" href="https://stac47.github.io/c/relocation/elf/tutorial/2018/03/01/understanding-relocation-elf.html">understanding-relocation-elf</a><br>3.<a target="_blank" rel="noopener" href="http://stffrdhrn.github.io/hardware/embedded/openrisc/2019/11/29/relocs.html">ELF Binaries and Relocation Entries</a><br>4.<a target="_blank" rel="noopener" href="http://chuquan.me/2018/06/03/linking-static-linking-dynamic-linking/">static-linking-dynamic-linking</a><br>5.<a target="_blank" rel="noopener" href="https://blog.csdn.net/ayu_ag/article/details/78655300">ELF函数重定位问题</a></p>

      
    </div>

    
    
    
      <footer class="post-footer">
        <div class="post-eof"></div>
      </footer>
  </article>
  
  
  


  
  <nav class="pagination">
    <span class="page-number current">1</span><a class="page-number" href="/archives/page/2/">2</a><a class="extend next" rel="next" href="/archives/page/2/"><i class="fa fa-angle-right" aria-label="下一页"></i></a>
  </nav>



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="wangduwei"
      src="/images/avatar.jpeg">
  <p class="site-author-name" itemprop="name">wangduwei</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">7</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">11</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="https://github.com/duweiwang" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;duweiwang" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:wangduwei8@gmail.com" title="E-Mail → mailto:wangduwei8@gmail.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
  </div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">wangduwei</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-chart-area"></i>
    </span>
      <span class="post-meta-item-text">站点总字数：</span>
    <span title="站点总字数">53k</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
      <span class="post-meta-item-text">站点阅读时长 &asymp;</span>
    <span title="站点阅读时长">48 分钟</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>








      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/medium-zoom@1/dist/medium-zoom.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/pisces.js"></script>


<script src="/js/next-boot.js"></script>




  
  <script>
    (function(){
      var canonicalURL, curProtocol;
      //Get the <link> tag
      var x=document.getElementsByTagName("link");
		//Find the last canonical URL
		if(x.length > 0){
			for (i=0;i<x.length;i++){
				if(x[i].rel.toLowerCase() == 'canonical' && x[i].href){
					canonicalURL=x[i].href;
				}
			}
		}
    //Get protocol
	    if (!canonicalURL){
	    	curProtocol = window.location.protocol.split(':')[0];
	    }
	    else{
	    	curProtocol = canonicalURL.split(':')[0];
	    }
      //Get current URL if the canonical URL does not exist
	    if (!canonicalURL) canonicalURL = window.location.href;
	    //Assign script content. Replace current URL with the canonical URL
      !function(){var e=/([http|https]:\/\/[a-zA-Z0-9\_\.]+\.baidu\.com)/gi,r=canonicalURL,t=document.referrer;if(!e.test(r)){var n=(String(curProtocol).toLowerCase() === 'https')?"https://sp0.baidu.com/9_Q4simg2RQJ8t7jm9iCKT-xh_/s.gif":"//api.share.baidu.com/s.gif";t?(n+="?r="+encodeURIComponent(document.referrer),r&&(n+="&l="+r)):r&&(n+="?l="+r);var i=new Image;i.src=n}}(window);})();
  </script>



  <script>
  if (CONFIG.page.isPost) {
    wpac_init = window.wpac_init || [];
    wpac_init.push({
      widget: 'Rating',
      id    : 31838,
      el    : 'wpac-rating',
      color : 'fc6423'
    });
    (function() {
      if ('WIDGETPACK_LOADED' in window) return;
      WIDGETPACK_LOADED = true;
      var mc = document.createElement('script');
      mc.type = 'text/javascript';
      mc.async = true;
      mc.src = '//embed.widgetpack.com/widget.js';
      var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(mc, s.nextSibling);
    })();
  }
  </script>












  

  



<script>
NexT.utils.loadComments(document.querySelector('#valine-comments'), () => {
  NexT.utils.getScript('//unpkg.com/valine/dist/Valine.min.js', () => {
    var GUEST = ['nick', 'mail', 'link'];
    var guest = 'nick,mail,link';
    guest = guest.split(',').filter(item => {
      return GUEST.includes(item);
    });
    new Valine({
      el         : '#valine-comments',
      verify     : false,
      notify     : false,
      appId      : '45lTcsdp8QJNGsmN5wEaOtV5-gzGzoHsz',
      appKey     : 'QsK8vR7pb8w0M1eIk7QE50yF',
      placeholder: "Just go go",
      avatar     : 'mm',
      meta       : guest,
      pageSize   : '10' || 10,
      visitor    : false,
      lang       : '' || 'zh-cn',
      path       : location.pathname,
      recordIP   : false,
      serverURLs : ''
    });
  }, window.Valine);
});
</script>


  <!-- 页面点击小红心 -->
  
        <script type="text/javascript" src="/js/love.js"></script>
  
</body>
</html>
